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={0n1n|n≥0} U {1n0n|n≥0} |
Break problem in two |
S1→0S11|ε
S2→1S20|ε |
Merge |
S→S1|S2
S1→0S11|ε
S2→1S20|ε |
Simplifications 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 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 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 symbol
S0→S |
Step 1: |
Remove Nullable variables (A→ε) and Unit productions (A→B) |
Step 2: |
For every symbol a add Ta→a |
Step 3: |
Replace A→C1C2...Cn with
A→C1V1
V1→C2V2
...
Vn-2→Cn-1Cn |
Chomsky form only has productions in forms
A→BC
A→a
Greibach Normal Form
All Productions have form: |
A→aV1V2..Vk : k≥0 |
Example |
S→abSb
S→aa |
S→aTbSTb
S→aTa
Ta→a
Tb→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: Apq→aArsb
For each state p add: App→ε
For each state-triple (p,q,r) add: Apr→ApqAqr |
For initial state and accept state:
→⓪ & 🅐 |
Add the production: 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 "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
ⓘ→σ,ε→∂→ⓚ→ε,∂→ε→ⓙ |
|
Created By
Metadata
Favourited By
Comments
No comments yet. Add yours below!
Add a Comment
Related Cheat Sheets
More Cheat Sheets by Vipera