Finite State Automata §
finite state machines.
the language of a fsa is the set of strings that are accepted by
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.
- same symbol may transition from one state to several different states
- -transitions are permitted
accept if at least one path accepts
- : symbols
- : states
- : initial state
- : accepting states
- transitions need not be unique
simulate NDFSA by BFS’ing
Minimal Machines §
DFSA that accepts a language with the fewest possible states. minimal DFSAs are unique.
“states are equivalence classes”
if is a DFSA that accepts , then the number of states in is greater than or equal to the number of equivalence classes of .
Theorem: if the number of equivalence classes of is finite, then there exists a DFSA that accepts , such that the number of states of equals the number of equivalence classes of . Therefore, is minimal.
Theorem: the minimal DFSA for a language is unique (up to state names).
Myhill-Nerode Theorem: There exists a DFSA that accepts a language if and only if the number of equivalence classes of is finite.
Regular Languages §
- if and
- , , (where )
- , , , where are regular expressions on
Theorem: A language can be recognized by a DFA if and only if can be represented by a regular expression.
Theorem: Regular languages are closed under , , , ,
Non-Regular Languages §
Lemma: is not regular
Regular Grammars §
- : non-terminal symbols
- : terminal symbols
- : rules
- : start symbol
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
- a countable union of finite sets is countable
- a countable union of countable sets is countable (cantor’s diagonalization)
Theorem: if is a finite alphabet, then (strings of finite length) is countable.
Context-Free Grammars §
ambiguity: more than one parse tree for the same string
- some languages are inherently ambiguous
- no algorithm for detecting ambiguity in all cases
- no algorithm for removing ambiguity in all cases
heuristics for removing ambiguity:
- eliminate rules
- eliminate symmetric recursive rules
- eliminate ambiguous attachments
chomsky normal form: rules have one of the following forms:
- where is a terminal
- where and are non-terminals
converting to chomsky normal form:
- remove rules
- remove unit rules (e.g. , where is not a terminal)
- remove mixed rules (e.g. or )
- remove long rules (e.g. where )
note: chomsky normal form may be ambiguous
Push-down Automata §
Deterministic PDAs are not equivalent to non-deterministic PDAs.
- for every cfg there exists an equivalent pda
- for every pda there exists an equivalent cfg
- pdas and cfgs describe the same languages
restricted normal form:
- has a new start state
- has a single accepting state
- every transition of (except from ) pops exactly on symbol off the stack