Quiz 02 (February, 6th)
Statistics
There were 2 problems, each worth 10 points.
- Min: 2
- Median: 12
- Max: 20
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:
- xyiz in L for all i >= 0;
- |y| > 0;
- |xy| <= p
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