Question

Question 1

Consider the language S*, where S = {ba bab bba}. Which one of the following words is in this language?

1. bbababb
2. babbaababa
3. babbbabbbabba
4. bababab

Question 2

Which one of the following is an example of two sets S and T of strings such that S  T and T  S, but S* ≠ T*?

1. S = {a, ab, bb} and T = {a, ab, ba, bb}
2. S = {a, aaa} and T = {a, aaa, aaaa}
3. S = {a, b} and T = {a, b, ab}
4. S = {a, b, ab, bb} and T = {a, b, ba, bb}

Question 3

Consider the language S*, where S = {bb, bab}. Which one of the following words is not in the language S*?

1. bbabb
2. babbb
3. bbbab
4. babbabbb

Question 4

Which one of the following is an example of a set S such that the language S* has less 5-letter words than 3-letter words?

1. S = {aaa, ba, a}
2. S = {aaa, aa, bb, a}
3. S = {aabba, aabb, bbb, aaa}
4. S = {babbb, b, bab}

Question 5

Consider the language EVENABAB over the alphabet ∑ = {a b} consisting of all words of even length that contain the substring abab. Which one of the following is a suitable generator?

1. abab
2. ab
3. a
4. 

Question 6

Consider the language MultipleOfFourNotAAandB consisting of all words of a length which is divisible by 4 without a remainder that do not contain an aa-substring but contains a b-substring. Which one of the following can be used as one of the generators of the language?

1. babababa
2. Λ
3. aaba
4. bab

Question 7

Which one of the following regular expressions generates a language equivalent to the language generated by (ab + ba)*?

1. (abba)*
2. ((ab)*(ba)*)*
3. (a + b)*
4. (aa + ab)*ba

Question 8 Which one of the following regular expressions defines the language of all strings that ends on an a- or an abbb-substring?

1. (a + b)*a + (a + b)*bbb
2. (a + b)*a(a + b)*bbb(a + b)*
3. (a + b)*a( + bbb)
4. (a + b)*(a + bbb)

Question 9

Which one of the following words cannot be generated by the regular expression? (b + a)*(ab + ba)(b) ?

1. abbabbb
2. babbbabab
3. baabbbbbab
4. babb

Question 10

Which one of the following regular expressions generates a language equivalent to the language generated by the regular expression? aaa*[(ab + babab)(a + b)* + ba]

1. aaa*(ab + babab)(a + b)* + ba(a + b)*
2. aaa*[ab(a*b*)* + babab)(a*b*)* + ba]
3. [aaa*ab + aaa*babab](a + b)* + ba
4. (a + b)* + ba

Answer 1

que.no.1:

answer option 2.

que.no.2:

answer option 3.

que. no.3:

answer option3