FSMs can't handle nested tags. Pushdown Automata can. | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		andrewf on Oct 6, 2010 \| parent \| context \| favorite \| on: Algorithm for converting a finite state machine in... FSMs can't handle nested tags. Pushdown Automata can.

qntm on Oct 6, 2010 [–]

Most "regular" expression engines in modern programming languages can handle back-references (e.g. "(.)\1"), which are actually so complex that you need a full-blown Turing machine to handle them.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact