1. (10 pts) For languages A={1,a,aa}, B={2,a,aa}, C={aa,aaa} over S ={1,2,a} find

1. ABÈ BC {12, 1a, 1aa, a2, aa, aaa, aa2, aaaa, 2aa, 2aaa, aaaaa}
2. CB-BC {aa2, aaa2}
3. A* A* = {1,a}*

1. (25 pts) (This is an essay question.) Discuss the relationships among nfa’s, dfa’s, regular expressions, regular languages, e -nfa’s, right regular grammars, and cfg’s.

As structures, every dfa is an nfa, every nfa is an e -nfa, and any e -nfa can be converted to an equivalent dfa, so all three are equivalent. A right regular grammar is a particular kind of cfg, but there are cfg’s whose languages cannot be the language of any right regular grammar. On the other hand, for any right regular grammar there is a dfa with the same language and conversely. Regular expressions are used to denote regular languages. For any regular expression there is a dfa with the same language and conversely. Summing up, the languages of dfa’s, nfa’s, e -nfa’s, regular expressions, and right regular grammars are all the same, and can all be given by a cfg, but there are some cfg’s which have languages which are not regular.

2. (25 pts) Prove one of the following:

1. The set A = { x | x is real and 0<x<1} is uncountable.

BWOC, assume (0,1) is countable Þ $ 1-1, onto f:N® A, where N is the set of natural numbers. Write f(i)=0.a_i1a_i2a_i3a_i4 …., where each a _ij is a digit between 0 and 1, and expansion of f(i) does not terminate (in a string of 0’s), e.g., if f(i) is 0.1, we write it as 0.0999999….

Let x=0.x₁x₂x₃x₄ ….. where each x_i is chosen from {1,2,…9}-{ a_ii}.

Then x_ii¹ a_ii for each i Þ x¹ f(i) for each i. Thus we have the contradiction that x is in A and f is 1-1 and onto.

2. The set of languages over a given alphabet is uncountable.

1. (20 pts) Given the nfa M=({s,1,2,3}, {a,b}, s, {2,3},

{(s,a,1), (s,a,2), (1,b,3), (1,b,2), (3,a,s), (3,b,2)} )

2. Find an e -nfa whose language is {a,b}*-L(M).

{(s,a,1), (s,a,2), (1,b,3), (1,b,2), (3,a,s), (3,b,2)} )

1. (15 pts) Prove that the following grammar is or is not LL(1).

The grammar is not LL(1) because A® e and

follow(A)Ç first(A) ={a,b,c} ¹ f

8. (15 pts) Find a dfa equivalent to the nfa, M, of problem 6.

a b

s 12 f

12 f 23

f f f

23 s 2

2 f f

The set of final states is {12, 23, 2}

9. (15 pts) Find a cfg in Chomsky Normal Form equivalent to the grammar:

S ® aAb | cAb | aBC

A ® a | aA | e

B ® bAA | e

C ® c | e

We first get rid of all the e -productions. That gives

S ® aAb | cAb | aBC | ab | cb | aC | aB | a

A ® a | aA

B ® bAA | bA | b

C ® c

Now we add S® XY, X® a, Y® AZ, Z® b, S® CY, S® XW, W® BC, S® XZ, S® CZ, S® XC, S® XB, A® XA, B® ZV, V® AA, B® ZA, and remove all "offending" productions to get

S ® XY | CY | XW | XZ | CZ | XC | XB | a

A ® XA | a

B ® ZV | ZA | b

C ® c

X ® a

Y ® AZ

Z ® b

W ® BC

V ® AA

10. (15 pts) Find a cfg with no unit productions equivalent to the grammar:

S ® ST | S | T

T ® TA | U

U ® a | b | cSc

Compute Unit(S)={S, T, U}, Unit(T)={T,U}, Unit(U)={U}.

For S® T add S® TAT|UT|TA

For S® U add S® aT|bT|cScT|a|b|cSc

For T® U add T® aA|bA|cScA

Toss out all unit productions to finally get

S® ST | TA | a | b | cSc

T® TA | a | b | cSc

U ® a | b | cSc

A ® ab

11. (15 pts) Find an nfa equivalent to the following e -nfa:

M = ({s,1,2,3}, {a,b}, s, {2,3},

{(s,a,1), (s,a,2), (1,b,3), (1,b,2), (3,a,s), (3,b,2), (s,e ,1), (1,e ,3)} )

We first add (s,e ,3). Then we add final states s and 1. Then

For (s,e ,1) add (s,b,2) and (s,b,3).

For (s,e ,3) add (s,b,2) and (s,a,s).

For (1,e ,3) add (1,b,2) and (1,a,s).

Now toss the e -transitions. We get D = {(s,a,1), (s,a,2), (1,b,3), (1,b,2), (3,a,s), (3,b,2), (s,b,2), (s,b,3), (s,a,s), (1,b,2), (1,a,s)} )

12. (10 pts) Fill out the table below by determining whether the given string is in the language from the given question and then state either YES (it is in the language) or NO (it is not in the language). For example, for the first row and first column determine whether aaaaa is in ABÈ BC, where A, B, and C are defined in question 3.