## Description

COMP 330 – Assignment 3

You should upload the pdf file (either typed, or a

clear and readable scan) of your solution to mycourses.

Answer only five questions of your choice

1. (20 points) Prove that the intersection of a context-free language C and a regular language R

over the same alphabet Σ is context-free.

2. (20 points) Either prove that the following language is context-free, or prove that it is not

context-free. Here Σ = {0, 1}.

L = {wwR | w ∈ {0, 1}

∗

} ∩ {w | w has the same number of 0’s and 1’s}.

3. (20 points) Either prove that the following language is context-free, or prove that it is not

context-free. Here Σ = {a, b, c, d}.

L = {w | w has the same number of a’s and b’s, and additionally the same number of c’s and d’s}.

For example accddb ∈ L.

1

4. (20 points) Give a description of a Turing Machine that decides the strings of the form “u < v”

where u and v are two positive integers in binary and the string is valid as an inequality. Here

the alphabet is {0, 1, <}. (For example 10 < 100 is in the language but 11 < 10 is not; Also note

that the leftmost digit of the binary representation of every positive integer is 1.) Explain why

your Turing Machine works. Your description can have high level lines such as “Scan the tape

to the right, until you see the first 0”.

5. (20 points) Prove that a single-tape Turing Machine that is not allowed to write on the input

portion of the tape can only recognize regular languages.

6. (20 points) Prove that a PDA that has access to two stacks is as powerful as a Turing Machine.

Such a PDA has labels on the transition arrows of the form (a, α, β → α

0

, β0

), meaning that read

an a from the input, pop an α from the first stack, β from the second stack, and push α

0 on the

first stack, and β

0 on the second stack.

2