4200 – Formal Languages
Midterm 2 Solution
Fall 2019
Nov 4, 2019 at 2:00 – 2:50pm
Student:
1
Midterm 2 Solution 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 in this question). For grading purposes, please use S as the starting variable. Alphabet Σ = {0, 1}.
1. A=∅ ∪{ε} ∪{0} Answer:
We realize that
Therefore, the CFG that generates A is:
A=∅ ∪{ε} ∪{0} = {ε} ∪ {0}
= {ε, 0}
S→ε|0 (1)
2. B={1i1j0k |i+j=kori+j=2k withi,j,k≥0} Answer:
We realize that
Therefore, the CFG that generates B is:
(2)
S→A|Z (3) A → 1A0 | ε (4) Z → 11Z0 | ε (5)
B={1i1j0k |i+j=kori+j=2k withi,j,k≥0} ={1k0k |k≥0}∪{12k0k |k≥0}
2
Midterm 2 Solution 4200 – Formal Languages (Instructor: Dr. ) Problem 2
Problem 2
30 points
For each of the languages below, please answer the following two questions:
(a) Is the language context-free or not?
(b) If context-free, please construct a corresponding pushdown automaton or a context-free grammar.
If not context-free, please show a proof using Pumping Lemma for context-free languages. For full credits, your proof need to include all the steps (e.g. the assumption, the choice of a string s, and etc. See examples in the book).
1. A = { (0i1i1m0m)k | i,m,k ≥ 0} Answer:
We realize that
A = { (0i1i1m0m)k | i,m,k ≥ 0} ={(0i1i1m0m)0 |i,m≥0} ={ε}
(6) ∪{(0i1i1m0m)1 |i,m≥0}∪{(0i1i1m0m)2 |i,m≥0}∪… (7)
∪{(0i1i1m0m)1 |i,m≥0}∪{0i1i1m0m0i1i1m0m |i,m≥0}∪… (8)
Idea: We further recognize that the third term in Eq. 8 is a not a context-free language because of 4 i’s and 4 m’s. That is, intuitively, with one stack of the PDA, it would be impossible to make sure four substrings to be of the same length i (the same constraint for 4 other substrings to be of the same length m).
Proof: Use pumping lemma for context-free languages.
Problem 2 continued on next page. . . 3
Midterm 2 Solution 4200 – Formal Languages (Instructor: Dr. )
Problem 2 (continued)
2. B=wRw|w∈{0,1}∗ Here,wR isthereverseofthestringw. Answer:
B is a context-free language and can be generated by the following CFG:
S → 0S0 | 1S1 | ε
(9)
4
Midterm 2 Solution 4200 – Formal Languages (Instructor: Dr. ) Problem 3
Problem 3
15 points
Given a language A = { 02n1n+1 | n ≥ 0 }. Please answer the following questions: 1. Is the above language regular or non-regular?
Answer: Non-regular.
2. Is the above language context-free or not? Answer: Context-free.
3. Please provide a model that recognizes or generates the language, if that is possible (choose one among the following five types: NFA, DFA, Regular expressions, Context-free Grammars, or ).
Otherwise, provide a proof by contradiction using one Pumping Lemma (choose either a Pumping Lemma for Regular languages or Pumping Lemma for Context-Free languages).
Answer: First, we recognize that A can be re-written as:
A={02n1n+1 |n≥0} (10) = { 02n1n1 | n ≥ 0 } (11)
Therefore, A can be generated by the following CFG:
S → B1 (12) B → 00B1 | ε (13)
The end.
5