Shreyas’ Notes

Automata, Formal Languages, and Computability

COMP 481

fall, senior year

Finite State Automata §

finite state machines.

the language of a fsa MM is the set of strings that are accepted by MM

L(M)={xΣM accepts x}L(M) = \{x \in \Sigma^* | M \textrm{ accepts } x\}

DFSAs can’t count.

Deterministic Finite State Automata §

Non-Deterministic Finite State Automata §

no more powerful than DFSA. can always be converted to an equivalent DFSA.

accept if at least one path accepts

M={Q,Σ,δ,q0,F}M = \{Q, \Sigma, \delta, q_0, F\}

simulate NDFSA by BFS’ing

Minimal Machines §

DFSA that accepts a language LL with the fewest possible states. minimal DFSAs are unique.

“states are equivalence classes”

if MM is a DFSA that accepts LL, then the number of states in MM is greater than or equal to the number of equivalence classes of LL.

Theorem: if the number of equivalence classes of LL is finite, then there exists a DFSA MM that accepts LL, such that the number of states of MM equals the number of equivalence classes of LL. Therefore, MM is minimal.

Theorem: the minimal DFSA for a language LL is unique (up to state names).

Myhill-Nerode Theorem: There exists a DFSA MM that accepts a language LL if and only if the number of equivalence classes of LL is finite.

Regular Languages §

Kleene closure:

Alternatively, L={x1x2xnxkL,n0}L^* = \{x_1 x_2 \dots x_n \mid x_k \in L, n \geq 0\}

Regular expressions:


Theorem: A language LL can be recognized by a DFA if and only if LL can be represented by a regular expression.

Theorem: Regular languages are closed under \cdot, ^*, \cup, \cap, C^C

Non-Regular Languages §

Lemma: L={0n1n}L = \{0^n 1^n\} is not regular

Regular Grammars §

G={N,Σ,R,S}G = \{N, \Sigma, R, S\}

rules for regular grammars:

non-terminals: states. terminals: transitions.

Theorem: the regular grammars define exactly the regular languages.

def regular_grammar_to_fsa(G):
	for n in non_terminals:
        create state for n
    	let S correspond to the start state

    create accepting state #
    for rule A → wB:
        add transition from state A to state B
    for rule A → w:
        add transition from state A to state #
    for rule A → ϵ:
        mark A as an accepting state

Theorem: if Σ\Sigma is a finite alphabet, then Σ\Sigma^* (strings of finite length) is countable.

Context-Free Grammars §

ambiguity: more than one parse tree for the same string

heuristics for removing ambiguity:

chomsky normal form: rules have one of the following forms:

converting to chomsky normal form:

  1. remove ε\varepsilon rules
  2. remove unit rules (e.g. ABA \rightarrow B, where BB is not a terminal)
  3. remove mixed rules (e.g. AaBA \rightarrow aB or ABaCA \rightarrow BaC)
  4. remove long rules (e.g. AB1BnA \rightarrow B_1 \cdots B_n where n>2n > 2)

note: chomsky normal form may be ambiguous

Push-down Automata §

Deterministic PDAs are not equivalent to non-deterministic PDAs.

restricted normal form: