Answer only. 36. Which of the following is a right regular grammar for the language represented by regular expression (a +b*)a?

A. S -> Ta; T -> a | U; U -> Ub | ?

B. S -> aa | aT; T -> bT | ?

C. S -> aa | T; T -> bT | ?

D. S -> aa | T; T -> bT | a

37. Which of the following languages is described by regular grammar S -> abS | c?

A. {c, ab, abab, ababab, , (ab)n, }

B. {c, abc, ababc, abababc, , (ab)nc, }

C. {c, cab, cabab, cababab, , c(ab)n, }

D. {?, abc, ababc, abababc, , (ab)nc, }

38. Which NFA is the resultant NFA transformed from the following grammar?

S ? aS | T

T ? bbT | ?

39. What is

the regular

grammar

transformed from

the

following NFA?

9

A. S -> T | aI

I -> bS

T -> cT | dF

B. S -> T | aI | ?

I -> bS

T -> cT | dF

F -> ?

C. S -> T | abS | ?

T -> cT | d

D. B and C above

40. Which of the following languages is not a regular language?

A. {?, a, b, aa, bb, aaa, bbb, , an, bn, }

B. {?, ab, aabb, aaabbb, , anbn, }

C. {?, ab, abab, ababab, , (ab)n, }

D. B and C above

41. What is a correct context free grammar for language { anbn+1 | n ? 0}

A. S -> aSb | ?

B. S -> aSb | b

C. S -> aSb | bb

D. S -> aSb | a

42. What is a correct context free grammar for the following language defined over the alphabet {a, b, c}:

L = {anbmck | n, m, k ? 0 and either n = m or m = k}.

A. S -> AB

A -> aAb | ?

B -> cB | ?

B. S -> AB

A -> aA | ?

B -> bBc | ?

C. S -> AB

A -> aAb | ?

B -> bBc | ?

D. S -> AB | CD

10

A -> aAb | ?

B -> cB | ?

C -> aC | ?

D -> bDc | ?

43. What is a correct context-free grammar for language {anbn | n ? 0}*?

A. S -> aSb | ?

B. S -> AS | A

A -> aAb | ?

C. S -> SA | ?

A -> aAb | ab

D. Both B and C

44. What is the language recognized by the following grammar?

S -> aSb | ?

A. {anbn | n ? 0}

B. {(ab)n | n ? 0}

C. {anbn | n ? 1}

D. {(ab)n | n ? 1}

45. Which production should be in the grammar for a language L = M ? N, where A is the start symbol for M and B the start symbol for N, and S is the start symbol for L?

A. S -> A | B

B. S -> AB

C. S -> AS | ?

D. S -> BS | ?

46. Which production should be in the grammar for a language L = MN, where A is the start symbol for M and B the start symbol for N, and S is the start symbol for L?

A. S -> A | B

B. S -> AB

C. S -> AS | ?

D. S -> BS | ?

47. Which production should be in the grammar for a language L = M*, where A is the start symbol for M, and S is the start symbol for L?

A. S -> AS | ?

B. S -> SA | ?

C. S -> AS | A

D. Either A or B

11

48. Which production should be in the grammar for a language L = M+, where + means concatenation of n strings in M and n ? 1, A is the start symbol for M, and S is the start symbol for L?

A. S -> AS | ?

B. S -> SA | ?

C. S -> AS | A

D. Either A or B

49. What is a correct context-free grammar for a language defined as {anbn | n ? 0} ? {anb2n | n ? 0}?

A. S -> A | B

A -> aAb | ?

B -> aAbb | ?

B. S -> AB

A -> aAb | ?

B -> aAbb | ?

C. S -> SA | B

A -> aAb | ?

B -> aAbb | ?

D. S -> SB | A

A -> aAb | ?

B -> aAbb | ?

50. What is a correct context-free grammar for a language defined as {anbn | n ? 0}{anb2n | n ? 0}?

A. S -> A | B

A -> aAb | ?

B -> aAbb | ?

B. S -> AB

A -> aAb | ?

B -> aAbb | ?

C. S -> SA | B

A -> aAb | ?

B -> aAbb | ?

D. S -> SB | A

A -> aAb | ?

B -> aAbb | ?