Assignment 4

COMP 330

There are 5 questions for credit and one for your spiritual growth. The

homework should be submitted through myCourses as a pdf in a single file.

Never submit a zip 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. Prove that any string generated by this grammar is a properly balanced

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

Alternate Question 2[15 points] Prove that the grammar in the previous

question generates only strings with the stated property and all strings with

the stated property.

Question 3[15 points] We define the language P AREN2 inductively as

follows:

1. ε ∈ P AREN2,

2. if x ∈ P AREN2 then so are (x) and [x],

3. if x and y are both in P AREN2 then so is xy.

Describe a PDA for this language which accepts by empty stack. Give all

the transitions.

Question 4[20 points] Consider the language {a

n

b

mc

p

|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 grammar. 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 straightforward 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.

Question 6[0 points] Show that the language L = {a

n

b

n

|n ≥ 0}∪{a

n

b

2n

|n ≥

0} is context free but is not accepted by any DPDA.

2

Sale!