Assignment 4
COMP 330 Winter 2021 McGill University
Due Date: 11th March 2021 18th February 2021
There are 5 questions for credit, one extra question to sharpen your ud- nerstanding and one for your spiritual growth. The homework should be submitted through myCourses as a pdf in a single file.
Question 1[25 points] A sequence of parentheses is a sequence of ( and ) symbols or the empty sequence. Such a sequence is said to be balanced if it has an equal number of ( and ) symbols and in every prefix of the sequence the number of left parentheses is greater than or equal to the number of right parentheses. Thus ((())()) is balanced but, for example, ())( is not balanced even though there are an equal number of left and right parentheses. The empty sequence is considered to be balanced.
Consider the grammar
S → (S)|SS|ε.
This grammar is claimed to generate balanced parentheses.
1. Provethatanystringgeneratedbythisgrammarisaproperlybalanced sequence of parentheses. [10]
2. Prove that every sequence of balanced parentheses can be generated by this grammar. [15]
Question 2[15 points] Consider the following context-free grammar S −→ aS | aSbS | ε
This grammar generates all strings where in every prefix the number of a’s is greater than or equal to the number of b’s. Show that this grammar is ambiguous by giving an example of a string and showing that it has two different derivations.
1
Question 3[15 points] We define the language PAREN2 inductively as follows:
1. ε∈PAREN2,
2. if x ∈ PAREN2 then so are (x) and [x],
3. ifxandyarebothinPAREN2 thensoisxy.
Describe a PDA for this language which accepts by empty stack. Give all the transitions.
Question 4[20 points] Consider the language {anbmcp|n ≤ p or m ≤ p}. Show that this is context free by giving a grammar. You need not give a formal proof that your grammar is correct but you must explain, at least briefly, why it works.
Question 5[25 points] A linear grammar is one in which every rule has exactly one terminal and one non-terminal on the right hand side or just a single terminal on the right hand side or the empty string. Here is an example
S → aS|a|bB; B → bB|b.
1. Prove that any regular language can be generated by a linear gram- mar. I will be happy if you show me how to construct a grammar from a DFA; if your construction is clear enough you can skip the straight- forward proof that the language generated by the grammar and the language recognized by the DFA are the same.
2. Is every language generated by a linear grammar regular? If your answer is “yes” you must give a proof. If your answer is “no” you must give an example.
Extra Question[0 points] Prove that the grammar in Question 2 gener- ates only strings with the stated property and all strings with the stated property.
Spiritual growth[0 points] Show that the language L = {anbn|n ≥ 0} ∪ {anb2n|n ≥ 0} is context free but is not accepted by any DPDA.
2