Fill This Form To Receive Instant Help
Homework answers / question archive / COMP 330 - Fall 2020 - Assignment 2 Due: 11:59pm Oct 8 th
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^{m}1^{n}|m ≥ 5 and n ≥ 0}.
( b )
{0^{n}|n is a Fibonacci number}.
1
2. (a) (3 points) Find a left-most derivation for aaabbabbba in the following context-free grammar:
S |
→ |
aB | bA |
A |
→ |
a | aS | bAA |
B |
→ |
b | bS | aBB |
(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}.
( a )
{0,1}^{∗}.
( b )
{0^{m}1^{n }| m ≥ n and m − n is even}.
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
[1] A prefix is a substring that starts from the beginning of the word.
Already member? Sign In