Show Menu
Cheatography

Automata - CFG & PDA Cheat Sheet by

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={01­n|n≥0} U {1nn­|n≥0}
Break problem in two
S1­→­0S­11|ε
S2→1S20|ε
Merge
S→S­1|­S2
S1→0S11|ε
S2→1S20|ε

Simpli­fic­ations of CFG

Substitution
(B →y1)
A→xBz
B→y1

A→xBz|xy1z
 
A→xBBz
B→y1

A→xBBz|xBy1z
|xy1Bz|xy1y1z
Removing ε
(B →ε)
A→xBz
B→ε

A→xBz|xz
Unit Production
(A →B)
A→B
B→bb
A→bb
B→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 δ(q­i,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 symbol
S0→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→C1­C...Cn with
A→C1V1
V1→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→aVV­2..Vk : k≥0
Example
S→abSb
S→aa
S→aTbSTb
S→aTa
Ta→a
Tb→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 consumed
The last state is an accepting state

PDA Formal­ities

PDA Repres­ent­ation
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→ε

"­Eas­y" PDA to CFG

For the pair of transitions:
ⓟ→­a,ε→t→­ⓡ ⓢ→­b,­t→ε→ⓠ
Add the produc­tion: Apq→aArsb
For each state p add: App→ε
For each state-­triple (p,q,r) add: Apr→­Ap­qAqr
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
ⓘ→σ,ε→∂→ⓚ→ε,∂→ε→ⓙ
                       
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

            Command Prompt Cheat Sheet Cheat Sheet by MakeUseOf
            Firefox for Mac Cheat Sheet Cheat Sheet by MakeUseOf

          More Cheat Sheets by Vipera

          Automata Cheat Sheet