Quiz 02 (February, 6th)

Statistics

There were 2 problems, each worth 10 points.

Problem 1

Formally state the Pumping Lemma for regular languages. Here is the start: For every regular language L there, exists an integer...

Solution

... p such that for every string w in L, |w| >= p, w can be split into three pieces, w = xyz, such that:

Problem 2

Give a CNF (Chomsky Normal Form) grammar for {aibj| i,j >= 0 }. Suggestion: First design a CNF grammar for {aibj| i,j >= 2 }, then add productions for shorter strings.

Solution

We can start e.g., with the following CNF grammar (e is the empty string):

  S -> AB
  A -> AA | a
  B -> BB | b
This grammar generates all the strings we are interested in, provided that at least one a, and one b occurrs in them. We can fix that problem by adding some more productions to the start symbol:
  S -> AB | AA | BB | a | b | e
  A -> AA | a
  B -> BB | b


February, 8th