Description
Question 1 (40 pts)
Formally define (in (K, Σ, Γ, ∆, s, F) form) and draw a PDA for each of the following languages.
1. {w#x | x
R is a substring of w for w, x ∈ {a, b}
∗}
2. {c
nwwRc
n
|w ∈ {a, b}
∗ ∧ n ≥ 0}
Note: w
R is the reversed form of the string w. To illustrate, given w = abcd, w
R = dcba.
Question 2 (30 pts)
It is known that the class of Context-free Languages is closed under Kleene Star. Give a counterexample
(with clear definition of a grammar) to show that for an arbitrary CFL L = L(G) where G = (V, Σ, R, S)
adding rule S → SS does not generate L
∗
.
Question 3 (30 pts)
Let us modify the definition of pushdown automata such that they have only one stack symbol. In the
scope of this homework, we will call this special type of PDA as S-PDA and the class of languages that
are recognized by S-PDAs as S-CFL (S-ContextFreeLanguages).
1. Which ones of the languages given below are S-CFLs? Briefly explain your reasoning for each.
• L1 = {a
n
b
n
|n ≥ 0}
• L2 = {w|w ∈ {a, b}
∗ and the number of a′
s in w is not equal to the number of b′
s in w}
• L3 = {a
n
b
m+n
c
m|m, n ∈ N}
2. Give another example of S-CFLs. Define the language with set definition and write the context-free
grammar that generates the language.
3. We can roughly say that PDAs are finite automata equipped with an (infinite) stack. Note that
S-PDAs are restricted in terms of computational power in comparision to the general PDAs. Then,
finite automata equipped with a smaller / less powerful memory element instead of a stack is should
be equivalent to S-PDAs in terms of computational power. What is that memory element? In other
words, try to find the minimal memory element that must be added to finite automata so as to
increase their computational power such that they will be able to recognize S-CFLs.
Remark1: Very brief answers are expected. Write only the name or the definition of the memory
element you proposed.
Remark2: You will get (potentially full) credit even if the memory element you proposed is not
the minimal possible alternative. However, is must have less capacity/power than an infinite stack.
Hint1: Notice that grammars generating S-CFLs have a similar restriction about non-terminal
symbols. While thinking, starting with this property may be helpful.
Hint2: Thinking through the NFA construction method may also help. This may help you to find
what property finite automata are lacking.
Hint3: Make use of non-determinism similarly as non-deterministic PDAs do.
Hint4: Given hints may or may not work for you. You may also find a valid answer with another
way of thinking.
2
4. What is the function of the memory element you added (to finite automata)? Why finite automata
must be extended with that element so as to be able to recognize S-CFLs? Explain briefly. Also
roughly explain the operational semantics of the machine type you designed (i.e. how it works) in
a few sentences.
5. Is the class of S-CFLs closed under complementation? If yes, give a sketch of proof. If no, give a
counterexample.
3
