Automata - CFG & PDA Cheat Sheet

A Programming › Algorithms cheat sheet in English by Vipera

Context Free Grammars, Pushdown Automata, Turing Machines

Context Free Automata Turing Grammars Pushdown Machines

13,305 views 2,077 downloads 12 Dec 2020 History

PRs

CFG Definition

Context-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 productions	{S→aSb, S→ε}

ONLY ONE variable → String of variables and terminals

Union of Two Languages

Example:	L={0ⁿ1ⁿ\|n≥0} U {1ⁿ0ⁿ\|n≥0}
Break problem in two	S¹→0S¹1\|ε S²→1S²0\|ε
Merge	S→S¹\|S² S¹→0S¹1\|ε S²→1S²0\|ε

Simplifications of CFG

Substitution (B →y¹)	A→xBz B→y¹	A→xBz\|xy¹z
	A→xBBz B→y¹	A→xBBz\|xBy¹z \|xy¹Bz\|xy¹y¹z
Removing ε (B →ε)	A→xBz B→ε	A→xBz\|xz
Unit Production (A →B)	A→B B→bb	A→bb B→bb
Useless Productions	A→aA (infinite)	∴ remove
	Unreachable from S	∴ remove

Step 1: Remove Nullable Variables
Step 2: Remove Unit-Production
Step 3: Remove Useless Variables

DFA to CFG

1. Create variable Rⁱ for every state qⁱ

2. Create rule Rⁱ → aR^j for every transition δ(qⁱ,a) → q^j

3. For accept states qⁱ create rule Rⁱ → ε

4. For initial state q⁰ make R⁰ the start variable

Conversion to Chomsky Normal Form

Step 0:	If start symbol (S) is on the right hand side, change start symbol S⁰→S
Step 1:	Remove Nullable variables (A→ε) and Unit productions (A→B)
Step 2:	For every symbol a add T^a→a
Step 3:	Replace A→C¹C²...Cⁿ with A→C¹V¹ V¹→C²V² ... V^n-2→C^n-1Cⁿ

Chomsky form only has productions in forms
A→BC
A→a

Greibach Normal Form

All Productions have form:	A→aV¹V²..V^k : k≥0
Example
S→abSb S→aa	S→aT^bST^b S→aT^a T^a→a T^b→b

PDA

Transitions: 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 computation such that:
All the input is consumed
The last state is an accepting state

PDA Formalities

PDA Representation	M=(Q,Σ,Γ,δ,q0,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}

CFG to PDA

Start with PDA of q0 →^ε,ε→S→q1 →^ε,$→$→q2

For each CFG production A→w add ε,A→w

For each CFG terminal a add a,a→ε

"Easy" PDA to CFG

For the pair of transitions:
ⓟ→^a,ε→t→ⓡ ⓢ→^b,t→ε→ⓠ

Add the production: A^pq→aA^rsb
For each state p add: A^pp→ε
For each state-triple (p,q,r) add: A^pr→A^pqA^qr

For initial state and accept state:
→⓪ & 🅐

Add the production: S→A^0a

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 "Easy" PDA

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

Badges

Downloaded from Unusual Locations × 1

Comments

No comments yet.