Languages Formels

TP5: Pushdown Automata

Exercise 1 (Pushdown Automata Example)

  • 1. Give a pushdown automaton that recognize the language L1 = { uũ | u ∈ Σ*}
  • 2. Give a pushdown automaton that recognize the Dyck language D*n
  • 3. Give a pushdown automaton that recognize the language L2 ={w ∈ {a,b}* | |w|a = 2 |w|b}
  • 4. Give a pushdown automaton accepting by empty stack that recognize the language L3 = { an bp | 1 ≤ n ≤ p ≤ 2 n }

    • Exercise 2 (Pushdown Automata Variants)

    Let A = (Q, Σ, Z, T, q0, z0, F) be a Pushdown Automaton.

  • 1. Show that it is possible to build a Pushdown Automaton A' recognizing the same language and such that T' ⊆ Q' × Z × (Σ ∪ {ε}) × Q' × Z≤ 2.
  • 2. Show that it is possible to build a Pushdown Automaton A'' recognizing the same language and such that every movement of the stack are of the form push, pop or skip.

    • Exercise 3

    We consider Pushdown Automata whose stack alphabet Γ is a singleton {z}.

  • a) Show that the language L={anbmc| n≥ m ≥ 1} can be recognized by a automaton accepting by empty stack and final state whose stack alphabet is a singleton.
  • b) Show that the language L={anbmc| n≥ m ≥ 1} cannot be recognized by a automaton accepting by empty stack whose stack alphabet is a singleton.

    • Exercise 4

  • 1. Let A = (Q,Σ,Z,T,q0,z0,F,K) be a Deterministic Pushdown Automaton accepting by top of the stack and by final state (i.e. a configuration (q,az) is accepting iff (q,z) ∈ K ⊆ Q × Z). Show that we can effectively build an equivalent Deterministic Pushdown Automaton accepting by final state.
  • 2. Let A be a Deterministic Pushdown Automaton. Show we can effectively build an equivalent Deterministic Pushdown Automaton whose ε-transitions are all of the form : (p,x) ε→ (q,ε).

    • Exercise 5 (Others Examples)

  • Show that the complement of the language L0 = { uu | y ∈ Σ*} can be recognized by a Pushdown Automaton.
  • Show that the complement of the language L1 = { uũ | u ∈ Σ*} can be recognized by a Pushdown Automaton.