CS402 Midterm Solved MCQs by Junaid

Q1. Which of the following steps replaces multiple incoming transition edges with a single one proving Kleene’s theorem part II?

1. Step 1
2. Step 2
3. Step 3
4. Step 4
5. Let FA1 accepts many strings and FA2 accepts no strings, then FA1+FA2 will be equal to:

a.FA1 b.FA2 C.FA2-FA1 d.(FA2)*

3. Let L be the language of all strings, defined over ∑ =(0,1), ending in 10. Which of the following strings are indistinguishable w.r.t L with z being 0? a.100.101

b.111.101 c. 110 .101 d.010.101

4. If r1=(aa+bb)and r2=(a+b) then the language (aa+bb)(a+b) will bhe generated by_______

a.(r1)(r2) b.(r1 +r2) c.(r2)(r1) d.(r1)*

5. Introducing a new start state in the case of multiple states is step no.______ of proving Kleen’s theorem part II.

a.1 b.2 c.3 d.4

Q6. The language having even numbers of a’s and even number of b’s defined over S={a,b} is called ______

1. EVEN-EVEN

B.ODD-ODD c. PALINDROME d. FACTORIAL

7. In NFA having no transition at a certain state, FA can be built by introducing :

a.Empty state b. Combination of states c .initial state d. final state

8. For every three regular expression R, S, and T. the language denoted by R(S U T) and (RS)U(RT) are the _______

a .same b. Different c. R(SUT)is greater d. none of the given options

Q9. Which of the following string belongs to the language of the regular expression (aa*b)?

1. baabab
2. abbbaa

c.aaaaaa d.aabaab

Q10. If L1’ and L2’ are regular languages, then L1, L2 will be

1. non regular
2. may be regular
3. Regular
4. none of the mentioned

Q11. Suppose the language L1 has 2 L2 has 2 states. If we have a machine M that accepts L1∩L2. Then the total number of states in M is equal to_______

1. 2
2. 4
3. 6
4. 8

Q12. If L is a regular language, then (L’)’ U L will be:

1. L

b. c.