Name: _______________________________, ___________________________________ (Last name) (First name)
Student ID#: __________________________________
Section: E
Instructor: Ali Mahmoodi
York University
Department of Electrical Engineering & Computer Science Lassonde School of Engineering
EECS 2001 E Quiz 2 (Version A) July 5, 2019
Guidelines and Instructions:
1. This is a 50-minute, closed-book test.
2. This exam paper has 5 pages (including this page) and 7 questions.
3. Print your name and write down your student number clearly.
4. If you need more space to write your answer use the back of the pages but clearly indicate which question you are answering.
5. You may not leave within the first and last 10 minutes of the exam. Remain seated until all exams are collected.
Question 1
/3
Question 2
/3
Question 3
/2
Question 4
/5
Question 5
/4
Question 6
/3
Total
/20
EECS 2001 Quiz 2 – Summer 2019 Section E
Question 1. [3 marks] Answer each question below for the following context-free grammar G.
𝐻 → 𝐻𝐻𝑌𝐻𝐻 | 𝑅
𝑅 → 𝑎𝑎𝑆𝑏𝑏 | 𝑏𝑏𝑆𝑎𝑎 𝑆 → 𝑌𝑆𝑌 | 𝑌 | 𝜀 𝑌→𝑎|𝑏
a) Give the three shortest strings in L(G)
Answer: aabb, bbaa, aaabb or aabbb (1.5 mark, 0.5 for each)
b) Give the three shortest strings not in L(G) Answer: ε, a, b (1.5, 0.5 for each)
Question 2. [ 3marks] Convert the following CFG to equivalent CFG in Chomsky normal form
𝑆 → 𝑎𝑆𝑏 | 𝜀
Answer:Anythingalongthelines:𝑆→𝑇𝑈|𝜀;𝑈→𝑆𝑇; 𝑇 → 𝑎; 𝑇 →𝑏. 𝑎𝑏𝑎𝑏
Notes: One may introduce rules of the form 𝑆0 → 𝑆 and then simplify the expressions which is correct. Up to 2 marks if the problem is partially correct.
Question 3. [2 marks] convert the following DFA to a context free grammar.
The left one: 𝑞1 → 0𝑞1 |𝜀,𝑞1 → 1𝑞2,𝑞2 → 1𝑞2,𝑞2 → 0𝑞1 (0.5 mark each) The right one:𝑞1 → 0𝑞1, 𝑞1 → 1𝑞2, 𝑞2 → 1𝑞2 |𝜀, 𝑞2 → 0𝑞1 (0.5 mark each)
Question 4. [5 marks] Give an informal English description of a PDA that accepts the following context free language:
{𝑎𝑛𝑏2𝑛 |𝑛 ≥ 0}
Answer: The PDA will start by pushing a special symbol, say $, on top of the stack and goes into a new state, say q1. While in q1 each time it reads input “a” it inserts two a’s on top of the stack. If in state q1 and it reads input b, it goes to a new state, say q2 and
Page 2 of 3
EECS 2001 Quiz 2 – Summer 2019 Section E
pops b . While in q2 and reading input b it pops a. If the machine reaches the end of input and the only thing left in stack is $, it pops $ and goes to accepting state.
One can also say push one a on top of the stack for each input a, but pop two b’s for each a on top of the stack. Both are possible.
Give full mark if solution is correct. Deduct mark for missing arguments, not stating the solution clearly.
Question 5. [4 marks] Give a context-free grammar that generates the following language.
{𝑎𝑛𝑏𝑛+𝑚𝑐𝑚|𝑚,𝑛 ≥0}
Answer: This is a context-free grammar. It is generated by the grammar shown below. The language can be written as 𝐿 = {𝑎𝑛𝑏𝑛𝑏𝑚𝑐𝑚 |𝑚, 𝑛 ≥ 0}. The following grammar generates the language:
𝑆→𝐴𝐵; 𝐴→𝑎𝐴𝑏|𝜀; 𝐵→𝑏𝐵𝑐|𝜀
Notes: 3 marks for correct grammar. Partial marks for attempts along the right path. Question 6. [3 marks] Show the grammar {𝑆 → 𝑎𝑆𝑏, 𝑆 → 𝑎𝑏𝑆, 𝑆 → 𝜀} is ambiguous.
Answer: Consider the two leftmost derivations for the string ab (1 mark). One using the rules 𝑆 → 𝑎𝑆𝑏, 𝑆 → 𝜀 and other using the rules 𝑆 → 𝑎𝑏𝑆, 𝑆 → 𝜀. These two have two different leftmost derivations and two different parse trees. (2 marks).
Page 3 of 3