Context Free Grammar

Formale definition - 4-tuple of Varibales (non-terminals) [V] and terminals (alphabet) sigma, a set of production rules [R] anda starting symbol/variable [S] which is typically the LHS of the first production rule

CFG from a regular language

First construct the DFA, Variables are states, transitions are production rules, if a state is accepting then that variable produces the empty string. Start state is the start variable.

Chomsky Normal Form

Languages of the form A->BC, A->a, s.t. B and C are not the start variable. S -> epsilon is permitted. Any CFL can be generated by a CFG in CNF. To transform CFG to CNF, createa start symbol that points to the old start symbol. Remove epsilon rules that are not the start symbol by replacing instances of the variable by its terminal for each instance that it appears in. Then remove the S_new -> S by replacein S with its production rules. Remove unit rules, then replace any more than 2 variable productions with new created rules until the conditions for CNF hold.

Pushdown Automaton Definition

the current state, next input symbol read, and top symbol of the stack determine the next move of a pushdown automaton. gamma is the stack alphabet which may be different from sigma the input alphabet. The transiton function is a function from the alphabets and state to the power set of states X gamma/stack alphabet. The other parts are the same (it is now a 6-tuple due to the extra alphabet)

String handle

the left most variable in a reduced string. D-CFG

DK Test

a DFA that can detect handles, used in proving the equiv of DCFG and DPDA along with the pumping lemma for DCFGs

LR(k) Languages

DCFG with lookahead 0 are equiv to LR(k=0) grammars. The k lookahead loosens the restriction on langauge designers making a deterministic language with forced handles in its grammar.