PROBLEM SET 3, CSC 280, 2006
DUE BEFORE CLASS, WED. FEB. 15
The third problem set is as follows. All 10 problems will be marked out
of the same total. Answers to any 7 (reduced from 8) questions make a
complete answer paper. However, you can do all questions to earn bonus points.
TO FACILITATE THE GRADING PROCESS, PLEASE PUT YOUR ANSWERS TO SEPARATE QUESTIONS
ON SEPARATE PAGES, AND PLACE YOUR ANSWERS IN THE SAME ORDER AS THE QUESTIONS,
I.E., ANSWERS TO Q1, ANSWERS TO Q2, ETC. THANK YOU!
Keep your eyes on the instructor's and the TAs' web site for any corrections
or discussion.
PROBLEM 1
~~~~~~~~~
Call a CFG 'recursive' if for some variable A there is a derivation A => x
where A occurs in x; call a variable A of a CFG with start symbol S
'unreachable' if A is not S and there is no derivation S => x where A
occurs in x; and call a variable A of a CFG 'unproductive' if there is
no derivation A => x where x is a terminal string. (A variable that
is either unreachable or unproductive is sometimes called "useless".)
a. Show that any CFG generates an infinite language only if it is recursive,
i.e., only if for some variable A there is a derivation A => x where
A occurs in x. (Hint: the most intuitive way to think about this
might be in terms of root-to-leaf paths in parse trees.)
b. Construct a CFG which is recursive, has no unreachable or unproductive
variables, and no productions A -> B (where A, B are variables),
yet generates a finite language containing at least two strings.
c. Convert your CFG from (b) to CNF, using the procedure covered in
class (and in the text).
Problem 2
~~~~~~~~~
Show that allowing regular expressions on the RHS of CFG rules still
yields only context-free languages. An example of such a generalized
rule would be
A -> (B U C)*a+,
where this can be thought of as standing for infinitely many rules
A -> a, A -> aa, ..., A -> Ba, A -> Baa, ..., A -> Ca, A -> Caa, ...,
A -> BBa, A -> BCa, A -> CBa, A -> CCa, A -> BBaa, A -> BCaa, etc.
Problem 3
~~~~~~~~~
The following grammar rules are used in the Sipser text, p. 108
(Example 2.10) to illustrate the conversion to CNF:
S -> ASA | aB, A -> B | S, B -> b | e (where e is the empty string)
a. Propose a simple characterization of the language generated by
these rules (where the start symbol is S); it should look like
this: L = {w | w fulfills some condition}.
Hint: Experiment with generating very short strings, to get a feel
for what can be generated.
b. Prove that your characterization is correct, using an inductive
argument. Hint: The basis of the induction should be concerned with
the shortest possible string(s), and the induction might then consider
the possibility of such derivations as S => aS and S => Sb.
PROBLEM 4
~~~~~~~~~
The proof used in the text that PDAs recognize all CFLs could be
viewed as based on top-down nondeterministic parsing (or as based
on leftmost derivations); similarly the proof used in class also
takes this perspective (though using CNF).
a. Provide an alternative construction based on bottom-up nondeterministic
parsing. Here is the general idea (steps 2-4 amount to a "reduction",
in parsing terminology):
0. Push $ onto the stack;
Repeat 1-4:
1. Shift 0 or more input symbols onto the stack;
2. Select a rule R: A -> x nondeterministically;
3. Match the symbols of x, in reverse order, against the stack
symbols (with no action required if x is epsilon);
{thus |x| stack symbols are consumed; match failure leads to
a deadend state -- which can be left implicit};
4. {All of x is matched} If A is the start symbol and the stack
symbol is $, restore the $, enter an accept state and push A
onto the stack; otherwise push A onto the stack without entering
an accept state.
b. Provide a proof that your PDA in part (a) recognizes the language
generated by the given CFG. Suggestions: Show that your PDA (in
effect) successfully cycles through steps 1-4, choosing a rule R
and placing a variable A on the stack (without otherwise altering
the stack), iff it has consumed a string from the input that is
derivable from A via rule R (as first step), since the time at
which the previous top-of-stack symbol (on which A is placed)
was added to the stack. For this proof, use induction on the
heights of parse trees for the derivation of a terminal string
from A via rule R.
PROBLEM 5
~~~~~~~~~
Consider the PDA M = ({q,q',q"},{a,b}, {A}, delta, q, {q',q"}), where
(with e denoting the empty string)
delta(q,a,e) = {(q,A)}, delta(q,e,e) ={(q',e)}, delta(q,b,A) ={(q",e)},
delta(q',e,A) = {(q',e)},
delta(q",b,A) = {(q",e)}, delta(q",e,A) ={(q",e)}.
a. Give the state diagram of M.
b. Concisely describe the language L(M) acepted by M .
PROBLEM 6
~~~~~~~~~
Construct PDAs that accept each of the following languages (where
a^i denotes "a repeated i times", & similarly for b^j, etc.):
a. {a^ib^j | i =/= j}
b. {w | w is in {a,b}* and has a prefix containing more a's than b's}
PROBLEM 7
~~~~~~~~~
Construct PDAs that accept each of the following languages:
a. {a^ib^jc^k | i+k = j}
b. {w | W is in {a,b}* and has twice as many a's as b's}
PROBLEM 8
~~~~~~~~~
Construct a PDA with only two stack symbols (say, Gamma = {0,1}) for
{wdw^R | w is in {a,b,c}*} (where w^R is the reverse of w).
PROBLEM 9
~~~~~~~~~
Construct a PDA for the grammar (with S as start symbol)
S -> aABA | aBB, A -> bA | b, B -> cB | c,
using the technique employed in proving that PDAs recognize the CFLs
(in class and in the book; the technique in the lecture slides depends
on use of Chomsky normal form). Remark: this grammar is in so-called
Greibach Normal Form; note that every production generates 1 terminal,
which is initial (but S -> e is allowed, as in CNF).
PROBLEM 10
~~~~~~~~~~
Consider the PDA M = ({q,q',q"},{a,b},{A},delta,q,{q"}), where
delta(q,a,e) = {(q,A)}, delta(q,b,A) ={(q',e)},
delta(q',b,e) = {(q",e)},
delta(q",b,A) = {(q',e)}.
a. Give the state diagram of M.
b. Give a concise description of L(M).
c. Calculate the number of grammar rules that result if the construction
in the proof that all PDAs recognize CFLs is applied. Do not write out
the rules -- this would be very tedious!