CREATE OWN LIBRARY

Application of DFA and NFA

Lexical Analysis: It match token by identifier by DFA or NFA

Text Editor: Like MS word. For matching we are using DFA or NFA

Spelling Checker: There exist a DFA for correct word and we match this DFA with what we written, if there any mistake it shows error message.

For sequential circuit design we can use DFA or NFA.

Search Command: In search there is a regular expression by which we search the pattern. Like : at Unix we are using grep command.

Limitation of finite automata (DFA or NFA):

Finite Automata has a finite memory.

1. It not process non-linear pattern like,

2. Comparison or count is not possible for infinite number like,

3. We can’t match string by FA like,

Variation of DFA and NFA

Difference between DFA and 2DFA:

1-DFA/DFA means $\mathbf{\delta }\mathbf{(}{\mathbf{q}}_{\mathbf{i}}\mathbf{ }\mathbf{,}\mathbf{ }\mathbf{a}\mathbf{)}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{q}}_{\mathbf{j}}$

In DFA machines read inputs left to right.

In 2-DFA machine read inputs left to right and right to left both sides.

$\mathbf{\delta }\mathbf{(}{\mathbf{q}}_{\mathbf{i}}\mathbf{ }\mathbf{,}\mathbf{ }\mathbf{a}\mathbf{)}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{(}{\mathbf{q}}_{\mathbf{j}}\mathbf{ }\mathbf{,}\mathbf{ }\mathbf{L}\mathbf{)}$ in transaction here should mention the position. L – L to R or R – R to L.

$\mathbf{\delta }\mathbf{(}{\mathbf{q}}_{\mathbf{i}}\mathbf{ }\mathbf{,}\mathbf{ }\mathbf{a}\mathbf{)}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{(}{\mathbf{q}}_{\mathbf{j}}\mathbf{ }\mathbf{,}\mathbf{ }\mathbf{L}\mathbf{)}$ i.e. after getting ${\mathbf{q}}_{\mathbf{j}}$ the top move and read from L to R. [Read top move left to right or right to left read input but it never writes.]