CS402 Midterm MCQs Set 2 by VU Topper RM

In FA, final state is represented by a ________ sign. A. - B. = C. *

D. +

If we have the regular expression (a+b)* (aaa + bbb) (a+b)*, then we can draw a TG for the provided RE with minimum _________ number of state(s). A. two B. zero C. one

D. three

Suppose we have the regular expression: aa(a+b+c)*bb(a+b+c)*cc Which of the following string will not be generated by the given RE? A. aabbcc B. aaaabbccbc C. aaabcbbcbacc

D. aaabbbbccc ok

If an FA has 3 states and 2 letters in the alphabet set, then it will have total ___________ number of transitions. A. 7 B. 4

C. 6 ok

D. 5

Which one of the following string is a part of EQUAL language defined over Σ={a,b}?

1. aabbaa
2. aabbbaa
3. ababab
4. babab

Correct answer: babab

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

Abbaab

Aaabab aaaababb

Which of the following statement is NOT true about TG?

There may exist NULL path There may be no final state

There exists exactly one path for certain string ok

There may exist more than one paths for certain string

Kleene’s Theorem Part III expresses the relationship between

A. RE and FA ok

B. FA and GTG C. TG and RE D. FA and TG

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

Aaababab

Babbba Abbbbaa bbabbbbaba

When even length language is expressed by an FA, then it will have minimum_______ states. One

Two

Four Three

FA stands for ___________. A. Fixed Automaton

B. Finite Automaton

C. False Automaton D. Functional Automaton

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

A. no transition at certain state ok

B. one transition at certain state C. two transitions at certain state D. more than two transitions at certain state

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

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: A. Only initial state of FA1 B. Final state of FA2 C. Only initial state of FA2

D. Initial state of FA1 or FA2 ok

Introducing new final state in case of multiple final states is the step no. ____________ of proving Kleene’s theorem part II.