CFG DefinitionContext-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 LanguagesExample: | 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 CFGSubstitution
(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 CFG1. 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 FormStep 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 FormAll Productions have form: | A→aV1V2..Vk : k≥0 | Example | S→abSb
S→aa | S→aTbSTb
S→aTa
Ta→a
Tb→b |
PDATransitions: 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 FormalitiesPDA 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 PDAStart 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 CFGFor 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" PDA1. 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