COMP 598  Assignment 3

COMP 598 
Assignment 3

Question 1[10 points]
A sequence of parentheses is a sequence of ( and ) symbols or the empty
sequence. Such a sequence is said to be balanced if it has an equal number
of ( and ) symbols and in every prefix of the sequence, the number of left
parentheses is greater than or equal to the number of right parentheses.
Thus ((())()) is balanced but, for example, ())( is not balanced even
though there are an equal number of left and right parentheses. The empty
sequence is considered to be balanced.
Consider the grammar
S → (S)|SS|ε.
This grammar is claimed to generate balanced parentheses.
1. Prove that any string generated by this grammar is a properly balanced
sequence of parentheses.
2. Prove that every sequence of balanced parentheses can be generated
by this grammar.
Question 2[10 points] Consider the following context-free grammar
S −→ aS | aSbS | ε
This grammar generates all strings where in every prefix the number of a’s
is greater than or equal to the number of b’s. Show that this grammar is
1
ambiguous by giving an example of a string and showing that it has two
different derivations.
Question 3[10 points] Prove that the grammar in the previous question
generates only strings with the stated property and all strings with the
stated property.
Question 4[10 points] We define the language P AREN2 inductively as
follows:
1. ε ∈ P AREN2,
2. if x ∈ P AREN2 then so are (x) and [x],
3. if x and y are both in P AREN2 then so is xy.
Describe a PDA for this language which accepts by empty stack. Give all
the transitions.
Question 5[10 points] Consider the language {a
n
b
mc
p
|n ≤ p or m ≤ p}.
Show that this is context free by giving a grammar. You need not give a
formal proof that your grammar is correct but you must explain, at least
briefly, why it works.
Question 6[10 points] A left-linear grammar is one in which every rule has
exactly one terminal and one non-terminal, with the terminal to the left of
the non-terminal, on the right hand side or just a single terminal on the
right hand side or the empty string. Here is an example
S → aS|a|bB; B → bB|b.
1. Prove that any regular language can be generated by a left-linear grammar. I will be happy if you show me how to construct a grammar from
a DFA; if your construction is clear enough you can skip the straightforward proof that the language generated by the grammar and the
language recognized by the DFA are the same.
2. If I allow the terminal on the right hand side to occur on the left or the
right of the non-terminal I have what is called a linear grammar. Is
every language generated by a linear grammar regular? If your answer
is “yes” you must give a proof. If your answer is “no” you must give
an example.
Question 7[10 points] The language {a
i
b
j
c
k
|i 6= j ∨ j 6= k} is easily seen to
be context-free. Give an outline of a PDA to recognize it. Show, however,
that it is not a deterministic CFL.
2
Question 8[10 points] Show that a language over a one-letter alphabet
is context free if and only if it is regular. Clearly any regular language is
context free so what you are being asked to prove is that any context-free language has to be regular. Hint: Use the pumping lemma for context-free languages to express the language as a finite union of regular languages.
Question 9[10 points] Give an example of a context-free language L such
that lefthalf(L) is not context free. The definition of lefthalf(L) is just as in
the regular case. Note the contrast with regular languaages.
Question 10[10 points] For each of the following assertions give brief arguments indicating whether they are true of false. In each case I am talking
about sets of positive integers.
a. For each n ∈ N we have a computable set Cn. The set [
n
Cn is
computable. We assume that the collection of computable sets is effectively given: this means that there is an algorithm that reads a
natural number n as input and outputs a description of a Turing machine that decides the set Cn. When you Google for the answer to this
question you will get the following argument which I will not accept:
Take any non-computable set S. It is the countable union of its singletons and each sinpleton is regular so clearly computable; hence the
statement is false. I don’t accept this argument because the family of
singletons is not effectively given in the sense above.
b. For each n ∈ N we have a computably enumerable set Cn effectively
given as described above. The set [
n
Cn is computably enumerable.
3