1.Write a proof by contradiction to show that the language, 

L= {an b2n | n ≥ 1} = {abb, aabbbb, aaabbbbbb, . . . } 

is nonregular. 

(Follow the example given in WBW section 6.1.2) 

2.Describe in words why the following languages over the alphabet, 

Σ= {a, b} 

are nonregular: 

 

 

     a) PAL = {palindromes} 

 

 

     b) EQAB = {strings that contain the same number of a's and b's} 

3.Consider the CFG

S  bS | aa

Prove that this generates the language defined by the regular expression: b*aa

 

 

4.Consider the CFG

S  aX

X  aX | cX | 

What is the language this CFG generates?

 

 

5.Consider the CFG

S  XpXpX

X  pX | qX | 

What is the language this CFG generates?

 

 

6.Find CFGs for the following languages over the alphabet  = {p q}

(i)All words in which the letter q is never tripled.

(ii)All words that do not have the substring pq.

 

 

 

 

7.Below is a set of words and a set of CFGs. For each word, determine whether the word is in the language of each CFG and, if it is, draw a syntax tree to prove it?

(i)aaaa

(ii)abaa

(iii)bbaa

 

 

CFG 1. 

S  aSb | ab

 

 

CFG 2

S  aS | bS | a

CFG 3

S  aS | aSb | X

X  aXa | a

 

 

CFG4

S  aAS | a

A  SbA | SS | ba

 

 

CFG5

S  aB | bA

A  a  | aS | bAA

Bb | bS | aBB

 

 

8.Show that the following CFGs are ambiguous by finding a word with two different distinct syntax trees.

(i) S  SaSaS | b

(ii) S  aaS  | aaaS | a

(iii) SAA

  A    AAA | a | bA | Ab

 

 

9.Show that the following CFGs that use  are ambiguous. Also find unambiguous CFGs that generate these languages.

 

 

(a)S  XaX

X  aX | bX | 

(b)S  aSX | 

X  aX | a

(c)S  aS |  bS | aaS | 

10.Begin to draw the total language trees for the following CFGs until we can be sure we have found all the words in these languages with one, two, three, or four letters. Which of these CFGs, if any, are ambiguous?

(a)S  aS | bS | a

(b)S  aSb | bX

X  bX | b

 

 

11.Find CFGs that generate these regular languages over the alphabet  = {a  b}.

(i)The language defined by (aaa + b)*

(ii)The language defined by (x + y)*(yyy + xxx)(x + y)*.   = {x  y}.

(iii)The set of all strings of odd length.  = {a  b}

(iv)All strings with exactly one a or exactly one b  = {a  b}

(v)All strings that end in p and have an even number of p’s in total.  = {p  q}.

(vi)All strings with [an odd number of a’s and any number of b's] OR [an even number of b’s and any number of a's].  = {a  b}.

 

 

CS375 Computation Theory
Assignment 6 1. Write a proof by contradiction to show that the language,
L= {an b2n | n ≥ 1} = {abb, aabbbb, aaabbbbbb, . . . }
is nonregular.
(Follow the example given in WBW section 6.1.2) 2. Describe in words why the following languages over the alphabet,
Σ= {a, b}
are nonregular:
a) PAL = {palindromes}
b) EQAB = {strings that contain the same number of a's and b's} 3. Consider the CFG
S bS | aa
Prove that this generates the language defined by the regular expression: b*aa
4. Consider the CFG
S aX
X aX | cX | What is the language this CFG generates?
5. Consider the CFG
S XpXpX
X pX | qX | What is the language this CFG generates?
6. Find CFGs for the following languages over the alphabet = {p q}
(i)
All words in which the letter q is never tripled.
(ii)
All words that do not have the substring pq.
7. Below is a set of words and a set of CFGs. For each word, determine whether the word is in
the language of each CFG and, if it is, draw a syntax tree to prove it?
(i)
aaaa
(ii)
abaa
(iii)
bbaa
CFG 1.
S aSb | ab
CFG 2
S aS | bS | a CS375 Computation Theory
Assignment 6 CFG 3
S aS | aSb | X
X aXa | a
CFG4
S aAS | a
A SbA | SS | ba
CFG5
S aB | bA
A a | aS | bAA
B b | bS | aBB
8. Show that the following CFGs are ambiguous by finding a word with two different distinct
syntax trees.
(i)
S SaSaS | b
(ii)
S aaS | aaaS | a
(iii)
S AA
A AAA | a | bA | Ab
9. Show that the following CFGs that use are ambiguous. Also find unambiguous CFGs that
generate these languages.
(a) S
X
(b) S
X
(c) S XaX
aX | bX | aSX | aX | a
aS | bS | aaS | 10. Begin to draw the total language trees for the following CFGs until we can be sure we have
found all the words in these languages with one, two, three, or four letters. Which of these
CFGs, if any, are ambiguous?
(a) S aS | bS | a
(b) S aSb | bX
X bX | b
11. Find CFGs that generate these regular languages over the alphabet = {a b}.
(i)
The language defined by (aaa + b)*
(ii)
The language defined by (x + y)*(yyy + xxx)(x + y)*. = {x y}.
(iii)
The set of all strings of odd length. = {a b}
(iv)
All strings with exactly one a or exactly one b = {a b}
(v)
All strings that end in p and have an even number of p’s in total. = {p q}. CS375 Computation Theory
Assignment 6 (vi) All strings with [an odd number of a’s and any number of b's] OR [an even
number of b’s and any number of a's]. = {a b}.

Attachments:

• 1493687309-help.doc