COMP 330 - Fall 2020 - Assignment 2

Due: 11:59pm Oct 8 th.

General rules: In solving these questions you may consult books or other available notes, but you need to provide citations in that case. You can discuss high level ideas with each other, but each student must find and write her/his own solution. Copying solutions from any source, com-

pletely or partially, allowing others to copy your work, will not be tolerated, and will be reported to the disciplinary office.

You should upload the pdf file (either typed, or a clear and readable scan) of your solution to mycourses.

1. (35 points) For each one of the following languages give a proof that it is or is not regular.

( a )

{0^m1ⁿ|m ≥ 5 and n ≥ 0}.

( b )

{0^m1ⁿ|m ≥ n²}.

3. The set of strings in {0,1}^∗ which are not of the form ww for some w ∈{0,1}^∗.
4. Over the alphabet Σ = {0,1}:
   50. = {x|x contains the same number of 01’s and 10’s as substrings}
5. Over the alphabet Σ = {0,1,2}:
   50. = {x|x contains the same number of 01’s and 10’s as substrings}
6. The first two Fibonacci numbers are 0 and 1, and each subsequent number is the sum of the previous two: 0,1,1,2,3,5,8,13,.... Now the language in question is

{0ⁿ|n is a Fibonacci number}.

1

7. The set of strings in {0,1}^∗ which are not palindromes:

{w ∈{0,1}^∗ | w 6= w^R}.

2. (a) (3 points) Find a left-most derivation for aaabbabbba in the following context-free grammar:

(b) (2 points) Draw the corresponding parse-tree of your left-most derivation. 3. (10 points) Show that the language of the grammar S → 0S1 | 1S0 | SS | ε is

{w ∈{0,1}^∗ | w contains the same number of zeros and ones}.

4. (20 Points) Construct a context free grammar for the set of all words w over the alphabet {0,1} such that each prefix^[1] of w has at least as many 0’s as 1’s. You have to prove that (i) every such word can be generated with your grammar, and (ii) every word generated by your grammar has the desired property.
5. (20 points) For each one of the following languages construct a context-free grammar that generates that language:

( a )

{0,1}^∗.

( b )

{0^m1ⁿ | m ≥ n and m − n is even}.

1. 3. The complement of {0ⁿ1ⁿ | n ≥ 0} over the alphabet {0,1}.
   4. The set of strings in {0,1}^∗ which are not palindromes:

{w ∈{0,1}^∗ | w 6= w^R}.

6. (10 Points) Use the equivalence of context-free grammars and push-down automata to show that if A and B are regular languages, then {xy|x ∈ A,y ∈ B,|x| = |y|} is context-free.

2