4200 – Formal Languages
Midterm 2
Fall 2018
Nov 2, 2018 at 2:00 – 2:50pm
Student:
1
Midterm 2 4200 – Formal Languages (Instructor: Dr. ) Problem 1
Directions: The test is open book and open notes, but NOT open electronic devices (e.g. phone, tablets or computers). For each problem, show your work completely. Your written reasons and explanations supporting your solutions will be graded.
There are 3 problems for a total of 65 points.
Problem 1
20 points
Define a context-free grammar that generates exactly each of the following languages. Both ambiguous and unambiguous grammars are acceptable (it does not matter). For consistency, please use S for the start variable.
1. A={0x1y0z |x=yory=z} Answer:
A is the union of two sets:
{0x1x0z |x,z≥0}∪{0x1z0z |x,z≥0} The CFG for A then is:
2. B={x|x∈{0,1}∗ } Answer:
S → AC | CB A → 0A1 | ε B → 1B0 | ε C → 0C | ε
S → 0S | 1S | ε
2
Midterm 2 4200 – Formal Languages (Instructor: Dr. ) Problem 2
Problem 2
40 points
Are the following languages context-free or not?
(a) If context-free, please show it by defining a pushdown automaton or a context-free grammar. (b) If not context-free, please show a proof via Pumping Lemma for context-free languages.
1. A={0n0n12m+1 |n,m≥0} Answer:
A is a context-free language, and below is a CFG for A.
S → AB A → 0C | ε C → 0A
B → 1D
D → ε | 1B
Problem 2 continued on next page. . . 3
Midterm 2 4200 – Formal Languages (Instructor: Dr. ) Problem 2 (continued)
2. B=wwRw|w∈{0,1}∗ Here,wR isthereverseofstringw. Answer:
B is not context-free. We will prove by contradiction via pumping lemma (PL) below.
First, assume B is a context-free language. Let p be the pumping length for B that is guaranteed to
exist by the pumping lemma.
We choose a string s = 0p110p0p1. Clearly, s is a member of B and of length |s| = 3p + 3 > p. Note that there are three blocks of 0’s in the original string 0p110p 0p1.
We recognize that regardless of how we break up the string s into five pieces uvxyz, it is impossible to include substrings of all of three blocks in |vxy| because according to Condition 3 in PL, |vxy| ≤ p. That is, vxy may contain parts of block 1 and block 2 or parts of block 2 and block 3, but never parts of all 3 blocks at the same time.
When we pump the string s up, we will always create more zeros in one block of 0’s than another. That will cause the resultant string s′ (e.g. s′ = uv2xy2z) to not be in the form wwRw and so s′ ̸∈ B, which contradicts Condition 1 of PL.
Therefore, B is not context-free.
4
Midterm 2 4200 – Formal Languages (Instructor: Dr. ) Problem 3
Problem 3
5 points
Convert the following CFG into an equivalent CFG in Chomsky Normal Form. Please show the result of each of four steps.
Note: Both procedures discussed in lecture or in the book are acceptable and should yield equivalent final grammars in CNF. You can choose either procedure.
S → T | ε | TST T → ε | 11
Answer:
The below is the final answer (for comparison).
S0 → TA1 | TS | ST | UU | TT | ε S → TA2 | TS | ST | UU | TT
T → UU
U→1 A1 → ST A2 → ST
However, the majority of your grade will come from you derive it by following the procedure.
The end.
5