# Prerequisite for the Parser Generator

Notes:

1. Double circles : accepting states.

Transition action:

There are 2 models doing it which depends upon on the application we can make use of it.

1.Non-deterministic finite automata(NDFA)

2.Deterministic finite automata(DFA)

**Non-deterministic finite automata(NDFA):**

The transition with the current input symbol(A) will have zero ,one or more possible state.

Transition Flow:

f(q,A)=q1.q2,q3..

Note: since it uses more state for single input, more memory is required.

**Deterministic finite automata(DFA):**

The transition with the current input symbol(A) will have only one possible state.

Transition Flow: f(q,A)=q1.

Application:

Parser generator(bison, lemon,yacc), lexical analyser(Flex), Database, XSLT or XSLTproc (converts xml to html or other format)

Note: since it used minimum state, less memory is required.

State transition diagram:

It can be also represented by directed graphs. It states how the flow from one state to other is performed with the current input symbol.