Formal Languages

TP4: Grammars

Exercise 1

Can a context-sensitive grammar generate the language Lprime= { ap | p is a prime number} ?

Exercise 2 (Ogden Lemma Applications)

  • 1. Show that the language Lcross={ an bm cn dm | n,m ≥ 0 } is not context-free.
  • 2. Show that the language Lcopy = { ww | w ∈ {a,b}* } is not context-free.
  • 3. Show that the language {an bn cp dp | n,p ≥ 0} is context-free but not linear.
  • 4. Show that the language {an bn cm |n,m ≥ 0} ∪ {an bm cm | n,m ≥ 0} is context-free and inherently ambiguous. We shall apply the lemma to the words aK+K! bKcK and aK bK cK+K! exhibiting two different derivation trees for aK+K! bK+K! cK+K!.

    Exercise 3

    Give the Chomsky normal form of the grammar ({S,A,B},{a,b},P,S) defined by the rules:

  • S → bA|aB
  • A → bAA|aS|a
  • B → aBB|bS|b

    Show that if a word u is generated by a non-terminal A, then there exists words u1 and u2 respectively generated by B and C such that A → BC ∈ P.

    Deduce an algorithm in O(n3) that, given a word u, where |u|=n, answer wether or not u can be generated by G.

    Exercise 4

    Consider the language L=LG(S) where grammar G is defined by S → aSSb+c. Show that every rationnal language included in L is finite.

    Exercice 5.

    Let K be a rationnal language and L a context-free language. Show that

  • 1. the inclusion K ⊆ L is undecidable ;
  • 2. the inclusion L ⊆ K is decidable