CS402 Quiz 1

Q1. Which one of the following word is not accepted by the given regular expression? (a+b)*(aaa+bbb)(a+b)*

1. abbaaabba
2. bababbbba
3. ababaaaab
4. baabaabba

Correct answer: baabaabba

Q2. Two FAs are said to be equivalent, if they ______________.

1. accept same language
2. none of the given options
3. accept different language
4. accept null string

Correct answer: accept same language

Q3. Reverse of string "YxwzYz" defined over Σ ={w,x,Y,z} is __________.

1. zYzxwY
2. zYzwYx
3. zYwzxY
4. zYzwxY

Correct answer: zYzwxY

Q4. If S = {a}, then S+ will be ___________.

1. {a, aaa, aaaaa, aaaaaaa,…}
2. {a, aa, aaa, aaaa,…}
3. {a, aaa, aaaa, aaaaa,…}
4. {aa, aaaa, aaaaaa, aaaaaaaa,…}

Correct answer: {a, aa, aaa, aaaa,…}

Q5. Which one of the following word is not accepted by the given regular expression? (a+b)*bba(a+b)*

1. babbba
2. aaababab
3. abbbbaa
4. bbabbbbaba

Correct answer: aaababab

Q6. In case of finite automaton there ________ be a transition on each _______ for every letter of the alphabet set.

1. may be, state
2. often, edge
3. must, state
4. must, edge

Correct answer: must, state

Q7. Which one of the following is the RE for the language defined over Σ= {a, b} having all the words starting with a?

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

Correct answer: a(a + b)*

Q8. The state where there is no way to leave after entry, is called _____________.

1. Davey John locker
2. empty state
3. null state
4. delay state

Correct answer: Davey John locker

Q9. a(a+b)*b + b(a+b)*a is the regular expression of language defined over Σ={a,b} that is ________.

1. starting with a and ending in b
2. starting with b and ending in a
3. starting with a and ending in a
4. starting with a and ending in b or starting with b and ending in a

Correct answer: starting with a and ending in b or starting with b and ending in a

Q10. Let S = {aa, bb}, then S* will have the _______ string.

1. bbaab
2. aabbbaa
3. Λ
4. abba

Correct answer: Λ