Theory of Computation: Solved Questions on Automata
DFA vs NFA: Key Differences
Deterministic Finite Automata (DFA) vs Nondeterministic Finite Automata (NFA):
Deterministic Finite Automata (DFA)
- For each input symbol, only one transition is possible.
- No ε (epsilon) transitions are allowed.
- The transition function gives exactly one next state.
- Easier to implement in code.
Nondeterministic Finite Automata (NFA)
- For one input symbol, multiple transitions may be possible.
- ε-transitions may exist.
- The transition function gives zero, one, or many next states.
- Easier to design.
Pumping Lemma for Regular Languages
Statement
If L is a regular language, then there exists a pumping length p such that any string w in L with |w| ≥ p can be written as:
w = xyz
such that:
- |xy| ≤ p
- |y| > 0
- xynz ∈ L for all n ≥ 0
English with a size of 9.55 KB