Formal Languages Exercise

Exercise 1 : Linear Languages and one-peak automata

A one-peak automaton is a pushdown automaton such that in every valid computation, the size of the stack do not increase strictly anymore once it has decreased strictly. The size of the stack can therefore increase (or remain the same) during a first step of the computation, then in the second step it can only decrease (or remain the same).

A Language is one-peak if and only if there exists a one-peak automaton that accepts it.

  • 1) Show that the language L={anbn|n ≥ 1} ∪ {anb2n|n ≥ 1} is linear.
  • 2) Show that L is one-peak.
  • 3) Show that the language K={bai1bai2b...bainb | n ≥ 1 and ∃ j,ij ≠ j} is a one-peak language.
  • 4) Show that every linear language is a one-peak language.