CS402 Grand Quiz by Junaid

CS402 GRAND QUIZ · Sr.N · o · MCQS · ANSWE · R

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

2. Let FA1 accepts many strings and FA2 accepts no strings, then FA1+FA2 will be equal to: FA1

3.

0?

(010,101)

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

5. Introducing a new start state in the case of multiple states is step no.______ of proving Kleen’s theorem part II. 6. The language having even numbers of a’s and even number of b’s defined over S={a,b} is called ______ EVEN-EVEN

7. In NFA having no transition at a certain state, FA can be built by introducing : Empty 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 _______ Same

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

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

11. 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_______ 12. If L is a regular language, then (L’)’ U L will be: L 13. In Mealy machine, the output depends on______ Present state and Present output 14. Strings x,y,z belongs to ∑* such that xz ∈ L but yz ∉ L where L ⊆ ∑* are: Distinguishabl e 15. Melay machine to increase the output string in magnitude by 1 is called: machine 16. Suppose we have FA3 (which is to FA1+FA2) then the final state of FA3 will be declared final if: It corresponds to any of the final states of FA1 or FA2 17. If we have the finite language and the number of states in the FA is n then the maximum number of letter in each word of the language that will be accepted by the given FA will be : n+1

18. Which of the following state is introduced while developing NFA for the closure of FA? An initial state which should be

19. Length of EVEN-EVEN language is_______ Even 20. If FA1 corresponds to (a+b)* then FA1 must accept_______ strings/strings. Every

21. In FA, initial stage is represented by : Drawing an arrowhead before the state 22. Which one of the following machine is represented as a pictorial representation with states and directed edges labeled by an input letter along with an output character? Mealy machine

23. Length of machine “AbBAbcd“ defined over ∑=(Ab,B,c,d) is_______. Five

24. An FA is a collection of: Finite states , finite transition and finite input letter 25. Given the language L={ab, aa, baa}, which of the following strings are in L*? i) abaabaaabaa ii) aaaabaaaa iii)baaaaabaaaab iv)baaaaabaa 1,2 & 4

26. In the context to make NFA for the concentration of FA1 and FA2 (FA1 accepting null string) which of the following option is correct? Final states in both FAs

27. Every ___ is a ___ as well, but the converse may not be true. FA, TG

28. NFA with null string has ____ initial state(s). One 29. While finding RE corresponding to a TG, we connect the new start state with the old start state by____ transition. Null

30. If S=(x). then S* will be_____. {^,x,xx,xxx,x xxx….} 31. The minimum length of string (except null string) of a language that starts and ends in the same letter will be: 32. If S={ab, bb} , then S* will not contain______. bbba 33. initial state? Moore machine 34. Which of the following diagram is very rigid in order to express any language? FA

35.

11?

111,101

36. Mealy machine can have ______ final states. Zero 37. In Moore machine , output is produced over the change of: States

38. Lets we have two regular expressions R1 ={xx+yy}and R2={x+y} . Which one of the following is the correct regular expression for the union of R1 and R2? (xx+yy)+ (x+y)