Theory of Computation: Automata, Grammars, and Turing Machines
Posted by Anonymous and classified in Mathematics
Written on in
English with a size of 2.37 KB
(a) Alphabet, String, and Language Definitions
- Alphabet (Σ): A finite, non-empty set of symbols. Example: Σ = {0, 1} or Σ = {a, b}.
- String: A finite sequence of symbols chosen from an alphabet. Example: 0110, abba.
- Language (L): A set of strings over an alphabet Σ. Example: L = {a, ab, aab, aaab, ...} = a⁺b over Σ = {a, b}. ε denotes the empty string (length 0).
(b) DFA vs. NFA
- DFA: For each state and input symbol, exactly one next state is defined. No ε-transitions are allowed.
- NFA: For each state and input symbol, zero, one, or more next states are possible. ε-transitions are allowed.
- Power: Both accept the same class of languages (Regular Languages). Every NFA can be converted to an equivalent DFA.
- Design: DFA usually has more states;