Deterministic and Non Determinstic Push Down automata

 

1. Context-Free Languages and Their Automata

  • Context-Free Languages (CFLs) are those generated by Context-Free Grammars (CFGs).

  • They are more powerful than regular languages, which are generated by finite automata.

  • Why finite automata are not enough?

    • A finite automaton has only finite memory.

    • Some CFLs (like { aⁿbⁿ : n ≥ 0 }) require counting an unbounded number of symbols.

    • Some others (like palindromes { wwᴿ }) require storing a sequence and matching it in reverse.

This motivates a stronger machine: the Pushdown Automaton (PDA).

  • A PDA is like an NFA but with an extra stack memory.

  • The stack provides unbounded storage but in a restricted LIFO (Last-In-First-Out) way.

2. Nondeterministic Pushdown Automata (NPDA)

  • Definition: An NPDA is like a nondeterministic finite automaton (NFA) with an added stack.

  • The PDA can:

    1. Read the current input symbol (or ε = empty move).

    2. Look at the top of the stack.

    3. Based on these, decide nondeterministically what to do:

      • Push a symbol onto the stack,

      • Pop the stack,

      • Or leave it unchanged.

  • Key Result :

    • Every CFL can be recognized by some NPDA.

    • Every NPDA recognizes a CFL.

    • Thus, NPDA ⇔ CFL.

So, nondeterminism is crucial: with it, PDAs exactly capture the family of CFLs.

3. Deterministic Pushdown Automata (DPDA)

  • A DPDA is restricted:

    • For any given configuration (state, input symbol, top of stack), there must be at most one possible move.

    • No nondeterministic choices are allowed.

    • No simultaneous ε-move and input-move from the same configuration.

  • Observation:

    • DPDAs cannot recognize all CFLs.

    • Example: The language { aⁿbⁿcⁿ : n ≥ 0 } is not CFL at all. But even within CFLs:

      • { aⁿbⁿ : n ≥ 0 } is deterministic.

      • Palindromes { wwᴿ } require nondeterminism, so not recognized by DPDA.

  • Key Result :

    • DPDA languages = Deterministic CFLs (DCFLs).

    • DCFLs ⊂ CFLs (proper subset).

4. Why the Distinction Matters

  • For regular languages, DFA = NFA (deterministic and nondeterministic are equivalent).

  • For context-free languages, DPDA ≠ NPDA.

  • This asymmetry is one of the main conceptual differences between finite automata and pushdown automata.

  • Programming Languages:

    • Most programming languages are designed to be deterministic context-free languages (DCFLs).

    • This is important because parsers (like LR, LL parsers) are based on deterministic PDAs.

5. Summary Table

MachineMemoryDeterminismLanguage ClassNotes
DFA/NFA        None (finite states                only)EquivalentRegular     Languages        DFA = NFA            
NPDA        Stack (LIFO)Nondeterminism allowedCFLs        NPDA ⇔ CFG
DPDA         Stack (LIFO)Deterministic onlyDCFLs ⊂ CFLs        Not all CFLs are             DCFLs

Key Difference (NPDA vs DPDA)

  • NPDA: δ may give multiple possible next moves (nondeterministic choices).

  • DPDA: δ must give at most one move for each configuration.

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