Want to contribute? Click here to suggest edits or additions.

Write a context free grammar for every rular language.

Every state is nothing but a rule. If δ(a,q_i) = q_j

then R_i → aR_j

R_j → ϵ if q_j ∈ F

And the Context free grammar is

• V = {R_j}
• Σ = Σ
• R given as above
• S is R₀

Contd.

Parse to check if Expr.

1. Initialise a Stack with $
2. Push S to a Stack
3. Branch and make stacks every possible rule
4. If left most element

Push Down automaton

Defn: It is a Tuple P = (Q, Σ, Γ, δ, q₀, F)

• Q is a finite set of “states”
• Σ is a finite set called the alphabet
• Γ is a finite set called the stack alphabet
• q₀ ∈ Q is start state
• F⊆Q
• δ: Q × (Σ∪{ϵ}) × (Γ∪{ϵ}) → 𝒫(Q × (Γ ∪ {ϵ})

Example

0^N1^N

Informal-

1. If read a zero, push to stack
2. If read a one, pop from stack
3. Accept if stack is empty

Formal

Build P = (Q, Σ, Γ, q₀, F, δ)