Answer
exactly three of the five questions presented below. Make sure you
answer briefly but clearly. Extraneous incorrect information will
cause the score for otherwise correct answers to be lowered.
No aid other than your textbook is allowed on this examination.
Pledge (Must be signed according to UF Honor Code)
On my honor, I have neither given nor received unauthorized aid in doing this assignment.
________________________________ (signature)
Examination Questions
- Give a context-free grammar generating the language of all strings
of sequences of properly nested parentheses. Note that strings
such as
((())) and ((())(()))()()
are in the language, but )))((( is not.
- Show (by construction of a PDA) that the intersection of a
context-free language with a regular language is context-free.
- Consider the class of machines (Q, S,
G, d, q0,
g0) in which the set of states
Q, input alphabet S, stack alphabet G,
transition function d, and the start state
q0 are as in the PDAs described by Sipser,
but there is a unique bottom of stack symbol
g0 that appears on the stack at the
beginning of the machine's operation.
Suppose such a machine accepts a string if it can pop the
bottom of stack symbol when input is empty.
What is the distinction between the class of languages accepted
by such a machine and the class of languages accepted by
PDAs.
- Is the language {
aibj#akbl
| i+j < k+l } context-free?
- Is the language {
0i1j0k
| i < j and j = k }
context-free?
This document is copyright 1998 by Joseph N. Wilson.