COMP4200 Formal Languages, HW3
Richard Chapman
27 Oct, 2014
The first five questions give languages over {0, 1}. In each case decide
whether the language is regular or not, and prove your answer is correct
1. The set of all strings x beginning with a non-null string of the form
ww.
2. The set of all strings x containing some non-null string of the form ww.
3. The set of odd-length strings over {0, 1} with middle symbol 0.
4. The set of strings in which the number of 0’s and the number of 1’s are
both divisible by 5.
5. The set of strings in which the number of 0’s is a perfect square.
6. Using mathematical induction, show that every string produced by the
CFG with productions
S → 0 | S0 | 0S | 1SS | SS1 | S1S
has more 0’s than 1’s.
7. Show that the CFG with productions
S → a | Sa | bSS | SSb | SbS
is ambiguous.
1

欢迎咨询51作业君