CS402 Midterm MCQs by Talha Sajid

Q1. . FA corresponding to an NFA can be built by introducing an empty state for a letter having

1. no transition at certain state
2. one transition at certain state
3. two transitions at certain state
4. more than two transitions at certain state

Correct answer: no transition at certain state

Q2. Σ={a,Aa,Abb}, then string aAaAbbAa has ________ length.

1. One
2. Two
3. Three
4. Four

Correct answer: Four

Q3. Languages generated by Kleene star are always ______________.

1. Finite
2. Infinite
3. Sometimes finite & sometimes infinite
4. None of the these

Correct answer: Infinite

4. In order to make NFA for the union of FA1 and FA2, the final state/ states

of:

a) both FAs should be linked b) both FAs should be left intact

c) FA1 have a transition to the final state of FA2

d) FA2 have a transition to the final state of FA1

Q5. Let S = {aa, bb} be a set of strings then s* will have

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

Correct answer: Λ

Q6. If r1 = (aa + bb) and r2 = ( a + b) then the language (aa + bb)* will be generated by

1. (r1)(r2)
2. (r1 + r2)
3. (r2)*
4. (r1)*

Correct answer: (r1)*

Q7. If a language can be expressed through FA, then it can also be expressed through TG.

1. True
2. False
3. Depends on language
4. None of the above

Correct answer: True

Q8. Suppose we have FA3 which is equal to the union of FA1 and FA2. Now the initial state of the FA3 will be equal to:

1. Only initial state of FA1
2. Final state of FA2
3. Only initial state of FA2
4. Initial state of FA1 or FA2

Correct answer: Initial state of FA1 or FA2

9. Introducing new final state in case of multiple final states is the step no.

____________ of proving Kleene’s theorem part II.

a) 4

b) 1 c) 2 d) 3

Q10. In proving Kleene Theorem II, circuits are reduced into:

1. asterisk
2. difference
3. both difference and asterisk
4. sum

Correct answer: sum

Q11. Finite Automaton (FA) has:

1. Zero or more final states
2. Exactly one final state
3. Not more than two final states
4. Exactly two final states

Correct answer: Zero or more final states

Q12. The formal language is also known as _________.

1. Semantic language
2. Informal language
3. Syntactic language
4. Normal language

Correct answer: Syntactic language

13. The language of all strings defined over alphabet set = {x, y} having triple

x’s or triple y’s will have the minimum strings with length of:

a) 1

b) 3

c) 4 d) 2