Cheatography

# Automata - CFG & PDA Cheat Sheet by Vipera

Context Free Grammars, Pushdown Automata, Turing Machines

### CFG Definition

 Contex­t-Free Grammar: G = (V,T,S,P) V: Set of variables {S} T: Set of terminal symbols {a,b} S: Start variable S P: Set of produc­tions {S→aSb, S→ε}
ONLY ONE variable → String of variables and terminals

### Union of Two Languages

 Example: L={0n1n|n≥0} U {1n0n|n≥0} Break problem in two S1→0S11|ε S2→1S20|ε Merge S→S1|S2 S1→0S11|ε S2→1S20|ε

### Simpli­fic­ations of CFG

 Substitution(B →y1) A→xBzB→y1 A→xBz|xy1z A→xBBzB→y1 A→xBBz|xBy1z|xy1Bz|xy1y1z Removing ε(B →ε) A→xBzB→ε A→xBz|xz Unit Production(A →B) A→BB→bb A→bbB→bb Useless Produc­tions A→aA (infinite) ∴ remove Unreac­hable from S ∴ remove
Step 1: Remove Nullable Variables
Step 2: Remove Unit-P­rod­uction
Step 3: Remove Useless Variables

### DFA to CFG

 1. Create variable Ri for every state qi 2. Create rule Ri → aRj for every transition δ(qi,a) → qj 3. For accept states qi create rule Ri → ε 4. For initial state q0 make R0 the start variable

### Conversion to Chomsky Normal Form

 Step 0: If start symbol (S) is on the right hand side, change start symbolS0→S Step 1: Remove Nullable variables (A→ε) and Unit produc­tions (A→B) Step 2: For every symbol a add Ta→a Step 3: Replace A→C1C2...Cn withA→C1V1V1→C2V2...Vn-2→Cn-1Cn
Chomsky form only has produc­tions in forms
A→BC
A→a

### Greibach Normal Form

 All Produc­tions have form: A→aV1V2..Vk : k≥0 Example S→abSbS→aa S→aTbSTbS→aTaTa→aTb→b

### PDA

 Transi­tions: a, b → c means when input is a, remove b from stack and add c If the automaton attempts to pop from empty stack then it halts and rejects input. A string is accepted if there is a comput­ation such that:All the input is consumedThe last state is an accepting state

### PDA Formal­ities

 PDA Repres­ent­ation M=(Q,Σ­,Γ,­δ,q­0,z,F) Q: States {q0,q1,q2} Σ: Input Alphabet {a,b} Γ: Stack Alphabet {a,b,\$} δ: Transition Functions δ(q,a,­w1)­={(­q2,w2)} q0: Initial State q0 z: Stack Start Symbol \$ F: Accept States {q2}

### "­Eas­y" PDA to CFG

 For the pair of transitions:ⓟ→­a,ε→t→­ⓡ ⓢ→­b,t→ε→ⓠ Add the produc­tion: Apq→aArsbFor each state p add: App→εFor each state-­triple (p,q,r) add: Apr→ApqAqr For initial state and accept state:→­⓪ & 🅐 Add the produc­tion: S→A0a
Easy PDAs:
• Have only 1 accept state
• When accepting a string, the stack is empty (only inital symbol)
• Each transition pushes or pops

### PDA to "­Eas­y" PDA

 1. The PDA has a single accept state Create new accept state and make ε,ε→ε transi­tions from old accept states to the new 2. Use new initial stack symbol # New initial state, that transi­tions to a new state with ε,ε→@ (auxiliary symbol) that transi­tions to the old initial state with ε,ε→\$ 3. On acceptance the stack contains only stack symbol # Old accept state transi­tions to new to new accept state with ε,@→ε, ανδ self loops with ε,x→ε where ∀x∈Γ-{@,#} 4. Transi­tions can't push and pop Replace any ⓘ→σ,a→b→ⓙ with ⓘ→σ,a→ε→ⓚ→ε,ε→b→ⓙ 5. 4. Transi­tions can't neither push nor pop Replace any ⓘ→σ,ε→ε→ⓙ with ⓘ→σ,ε→∂→ⓚ→ε,∂→ε→ⓙ