CSC 473
Instructions:
Name________________________________
Midterm 2
• You may use your text for this exam but you may not use anything else.
• Your work MUST be your own. Consulting with anyone or searching the Internet is cheating and
if you are caught you will get a zero.
• Please write legibly and answer each question completely.
• You may print out this exam to fill in, or you may read it from a terminal and write your answers
on a separate piece of paper. Either way you must create a pdf of your answers and submit them to GradeScope by 2:00PM.
Glossary:
In this exam I use many abbreviations. I have used these throughout the lectures, so hopefully they won’t throw you off. Still, I’m defining them here in case you forgot:
• CFG – Context Free Grammar
• CFL – Context Free Language
• CNF – Chomsky Normal Form
• DFA – Deterministic Finite Automaton
• DPDA – Deterministic Pushdown Automaton
• NFA – Nondeterministic Finite Automaton
• PDA – Pushdown Automaton
• RE – Regular Expression
• RL – Regular Language
1. (10 pts) Use the pumping lemma to show that A = {0n/21n0n/2: n ∈ {0, 2, 4, 6, …}} is not a CFL.
2. (15 pts) Showing every step, convert the following CFG to Chomsky Normal Form. Be sure to show all your work and clearly label all your steps.
S → aBS | bAS | C
B → aBB | b
A → bAA | a
C → cC | ε
3.
(8 pts) Let A = B ⋂ C (no need to prove your answer)
a. Show values for A, B, and C such that A is a CFL, but neither B or C is
b. Show values for A, B, and C such that B is a CFL, but neither A or C is
4.
(8 pts) Show or Disprove: If A is a CFL and B is a RL, then A ⋃ B is a CFL. (argument can be informal, but should be convincing)
5.
(8 pts) Prove or Disprove: If A and B are CFL, then A – B is a CFL.
6. (10 pts) Let the CFG G be given by the following grammar:
S → SaS | SbS | c | ε
a. Give a left-most derivation for the string acb
b. Is G ambiguous? (Justify your answer)
c. Use the construction used to prove that ∀ CFG ∃ PDA P s. t. L(G) = L(P) to convert the CFG G to a PDA.
7. (8 pts) Write a state diagram for a PDA that accepts the language {Oj1kOj: j,k ≥ 0 and k is odd}. Do not use more than 6 states.
8. (8 pts) Write a CFG that generates the language
L={wcn:w ∈ {a,b}*andthenumberofa’sinwisnorthe number of b’s in w is n}
(e.g. babc ∈ L, abbcc ∈ L, ababbccc ∈ L, but abcb ∉ L and abcc ∉ L)
9. (5 pts) Prove or disprove. If A and B are CFLs and A ⊆ C ⊆ B, then C is a CFL
10. (10 pts) Refer to the PDA P whose state diagram is above:
a. Give a string accepted by P
b. Give a string that is not accepted by P
c. Give a description of L(P) which makes clear what the set is.
d. Assuming missing transitions go to the dead state, ∅, can we think of P as being a DPDA? Why or why not?
11. (10 pts) Answer the following True or False:
a. ∀PDAP∃CFGGsuchthatL(P)=L(G)
b. ∀ NFA N, ∃ CFG G in CNF such that L(N) = L(G)
c. If a CFG is in CNF, then it is unambiguous. (i.e. G is in CNF => G is unambiguous)
d. If L is a CFL and L’ is a RL then LL’ (concatenation) is a RL. (i.e.L∈CFLandL’∈RL=>LL’∈RL)
e. ∀ CFG G that is in CNF, ∃ DFA D such that L(G) = L(D).