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.