Non Deterministic Push Down Automata and Context Free Languages

 

📌 NPDA

The relationship between pushdown automata (PDA) and context-free languages (CFLs) is exactly analogous to the relationship between finite automata and regular languages:

  • Every CFL can be accepted by some nondeterministic PDA (NPDA).

  • Every language accepted by a NPDA is a CFL.

So:

{Languages accepted by NPDAs}={Context-Free Languages}\{ \text{Languages accepted by NPDAs} \} = \{ \text{Context-Free Languages} \}

This is why PDAs are the machine model for CFLs.

📌 Direction 1: From CFG → NPDA

We want to show: For every context-free grammar, there is an NPDA that accepts the same language.

Key Idea

  • A PDA has a stack, which is like "memory".

  • To accept a CFL, the PDA can simulate the derivation of the grammar using the stack.

  • For simplicity, we use a grammar in Greibach Normal Form (GNF):

    A  →  aX1X2⋯XkA \;\to\; aX_1X_2 \cdots X_k

    This form is useful because every production begins with a terminal, which matches nicely with how the PDA reads input.

Construction

  1. The PDA pushes the start symbol onto the stack.

  2. At each step, it looks at the top of the stack:

    • If the top is a variable (nonterminal), the PDA nondeterministically chooses a production rule and replaces the variable with its RHS (pushes the RHS).

    • If the top is a terminal and matches the next input symbol, the PDA pops it and consumes the input.

    • If there is a mismatch, that branch fails.

  3. If the input is completely read and the stack is empty, the PDA accepts.

📌 Direction 2: From NPDA → CFG

Now we show: Every language accepted by an NPDA is context-free.

Idea

  • Suppose we have an NPDA MM.

  • We want to construct a CFG GG such that L(G)=L(M)L(G) = L(M)

  • The grammar simulates the moves of the PDA.

The trick:

  • A variable of the form [pAq][p A q] means: “the PDA can go from state pp with AA on top of the stack to state qq after completely processing that portion of input.”

  • Productions are added to capture the possible transitions.

Though technical, the result guarantees that for every PDA, there exists such a CFG.

📌 The Two Major Results 

  1. For every context-free language, there exists a nondeterministic PDA that accepts it.

  2. For every nondeterministic PDA, the language it accepts is context-free.

Thus, CFLs = Languages accepted by NPDAs.

⚠️ Note: This equivalence only holds for nondeterministic PDAs.
Deterministic PDAs (DPDA) accept only a proper subset of CFLs, called deterministic CFLs (important in programming languages).

✅ In summary:
Pushdown Automata are the machine counterpart of context-free languages. The stack in a PDA provides the necessary unbounded memory to handle things like balanced parentheses, matching a^n b^n, or palindromes, which finite automata cannot manage.

Comments

Post a Comment

Popular posts from this blog

Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

About Me Course Details and Syllabus Theory of Computation PCCST302 Model Question Paper and Answers Module-1 Foundations of Finite Automata Motivation-Computability Need for Mathematical Modelling and automata Introducing automata     on-off switch     coffee vending machine Alphabet, Strings, and Languages Formal Definition of Finite Automata Deterministic Finite Automata - DFA Dead state in DFA Categories of DFA      Category 1: Accept Only the Given Input      Category 2: Starts and ends with      Category 3: Contains substring      Category 4: Specific length     Category 5: Divisibility ( Binary Numbers) Examples  DFA( University Questions) DFA Implementation C Program Non Deterministic Finite Automata - NFA Epsilon NFA  (∈-NFA) Examples NFA( University Questions) Regular Languages Epsilon Closure of NFA Eliminating Epsilon Transitions from NFA Epsilon Free NFA to DFA Conversion -...
Read more

Non deterministic Finite Automata NFA

Image
  🤖 Formal Definition of NFA An NFA (Nondeterministic Finite Automaton) is a theoretical machine used to recognize regular languages , like a DFA, but it allows multiple transitions for the same input or even no input at all (ε-transitions) . 📘 An NFA is defined as a 5-tuple : M = ( Q , Σ , δ , q 0 , F ) M = (Q, \Sigma, \delta, q_0, F) Where: Symbol Description Q Q A finite set of states Σ \Sigma A finite set called the input alphabet δ \delta The transition function : δ : Q × ( Σ ∪ { ε } ) → 2 Q \delta: Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^Q  (a set of states) q 0 q_0 ​ The initial state , q 0 ∈ Q q_0 \in Q F F The set of accepting states , F ⊆ Q F \subseteq Q 💡 Key Differences from DFA: DFA NFA Only one transition per input                Multiple transitions possible No ε-transitions                ε-transitions allowed Deterministic      ...
Read more

Formal Definition - Turing Machine

Image
  📘 Formal Definition - Turing Machine A Turing Machine is a nine-tuple M = ( Q , Σ , Γ , δ , B , ⊢ , s,t, r) M = (Q, \Sigma, \Gamma, \delta, s_0, B, ⊢, s_{acc}, s_{rej}) where: Q – a finite set of states (typically denoted r , s , t , ... ). Σ – the input alphabet , which does not contain the blank symbol B or the left-end marker ⊢ . Γ – the tape alphabet , satisfying Σ ⊆ Γ , B ∈ Γ , ⊢ ∈ Γ Σ ⊆ Γ, \quad B ∈ Γ, \quad ⊢ ∈ Γ Every cell of the tape contains one symbol from Γ. δ – the transition function δ : ( Q − { t,r } ) × Γ → Q × Γ × { L , R } δ : (Q - \{s_{acc}, s_{rej}\}) \times Γ \to Q \times Γ \times \{L, R\} Given the current state and the symbol under the tape head, the machine writes a symbol, moves Left (L) or Right (R), and enters a new state. s ∈ Q – the initial (start) state . B ∈ Γ – the blank symbol , representing the empty tape cell. ⊢ ∈ Γ – the left-end marker , which appears at the extreme left of the tape and is never overwritte...
Read more