Theory of Automata

Contents

Theory of Automata – CS402

Question No: 1    ( Marks: 1 )    – Please choose one

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

► One

► Two

► Three

► Four         

Question No: 2    ( Marks: 1 )    – Please choose one

Languages generated by kleene star are always                              .

► Finite

► Infinite         

► Sometimes finite & sometimes infinite

► None of the these

Question No: 3    ( Marks: 1 )    – Please choose one

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

► Λ       

► abba

► aabbbaa

► bbaab

Question No: 4    ( Marks: 1 )    – Please choose one

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

► (r1)(r2)

► (r1 + r2)

► (r2)*

► (r1)*           

Question No: 5    ( Marks: 1 )     – Please choose one

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

► True

► False

► Depends on language

► None of the above

Question No: 6   ( Marks: 1 )     – Please choose one

GTG can have                                final state.

► 0

► 1

► More than 1

► All of the given

Question No: 7    ( Marks: 1 )     – Please choose one

In GTG, if a state has more than one incoming transitions from a state. Then all those incoming transitions can be reduced to one transition using                                 sign

► –

► +

► *

► None of the given

Question No: 8    ( Marks: 1 )     – Please choose one

“One language can be expressed by more than one NFA”. This statement is                              .

► False

► True

► Depends on NFA

► None of the given

Question No: 9   ( Marks: 1 )     – Please choose one

One FA has 3 states and 2 letters in the alphabet. Then FA will have                        number of transitions in the diagram

► 4

► 5

► 7

► 6

Question No: 10 ( Marks: 1 ) – Please choose one

If an alphabet has n number of letter, then number of strings of length m will be

►n+m

► (n)(m)

►m^n

►n^m

Question No: 11 ( Marks: 1 ) – Please choose one

If a language is expressed through TG, then that language will have its RE.

►True

►False

►Depends on language

►None of these

Question No: 12 ( Marks: 1 ) – Please choose one

In TG there may exist more than one path for certain string.

►True

►False

►Depends on the language

►None of these

Question No: 13 ( Marks: 1 ) – Please choose one

In TG there may exist no paths for certain string.

►True

►False

►Depends on the language

►None of these

Question No: 14 ( Marks: 1 ) – Please choose one

Every FA should be                     

►Deterministic

►Non- Deterministic

►Deterministic & Non- Deterministic

►None of these

Question No: 15 (Marks: 1) – Please choose one

Auto Meta mean

► Manual work

► Automatic work

 Question No: 16 (Marks: 1) – Please choose one

S= {a,bc,cc} has the latters

► 1

► 2

3

► 4

Question No:17 (Marks: 1) – Please choose one

S={a,bb,bab,baabb} set of strings then S* will not have

► baba

► baabbab

► bbaaabb

► bbbaabaabb

Question No: 18 (Marks: 1) – Please choose one

One language can represents more than one RE.

► True

► Falss

► Can’t be assumed

► Non of given

Question No: 19 (Marks: 1) – Please choose one

The clouser FA*(star on an FA ) always accept              string

► Null

► aa

► bb

► None of given

Question No: 20 (Marks: 1) – Please choose one

In FA final state represent by                   sign

► +

► –

► =

► *

Question No: 21 (Marks: 1) – Please choose one

In FA one enter in specific stat but there is no way to leave it then state is called

► Dead States

► Waste Baskets

► Davey John Lockers

► All of above

Question No: 22 (Marks: 1) – Please choose one

Using tree structure final state represent by

► *

► –

► double circle

► None of given

Question No: 23 (Marks: 1) – Please choose one

Length of strings, generated by infinite language is              

►finite

►infinite

►none of these

Question No: 24 (Marks: 1) – Please choose one

RE for the language defined over Σ={a,b} having words starting with a is        

►a(a+b)*

► (a+b)*a

► (a+b)*

►None of these

Question No:25 (Marks: 1) – Please choose one

TG is always deterministic.

►True

►False

 Question No: 26 (Marks: 1) – Please choose one

The length of output string in case of                    is one more than the length of corresponding input string.

►Finite Automaton

►TG

►GTG

Question No: 27 ( Marks: 1 ) – Please choose one

“Every finite language can be expressed by FA”. This statement is                      .

►True

►False

►Depends on language

►None of these

Question No: 28 ( Marks: 1 ) – Please choose one

In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called

►Dead States

►Waste Baskets

►Davey John Lockers

►All of these

Question No: 29 ( Marks: 1 ) – Please choose one

In TG there may exist no paths for certain string.

►True

►False

►Depends on the language

►None of these

Question No: 30 ( Marks: 1 ) – Please choose one

In GTG’s there may exist no path for a certain string.

►True

►False

►Depends on alphabet

►None of these

Question No: 31 ( Marks: 1 ) – Please choose one

In TG, there may be a transition for null string.

►True

►False

►Can’t show transition for string

►None of these

Question No: 32 ( Marks: 1 ) – Please choose one

The                machine helps in building a machine that can perform the addition of binary numbers.

►Incrementing

►Complementing

►Decrementing

►None of the given

Question No: 33 ( Marks: 1 ) – Please choose one

►GTG can have                            initial state.

►Zero

►One

►More than One

►One OR more than One

Question No: 34 ( Marks: 1 ) – Please choose one

One FA has n states and m letters in the alphabet. Then FA will have         _ number of transitions in the diagram.

► (n)+(m)

► (m)(n) OR (n)(m)

►None of the given options

► (m)-(n)

Question No: 35 ( Marks: 1 ) – Please choose one

If L1 and L2 are expressed by regular expressions r1 and r2, respectively then the language expressed by r1 + r2 will be                        

►Regular

►Ir-regular

►Can’t be decided

►Another Language which is not listed here

Question No: 36 ( Marks: 1 ) – Please choose one

According to 3rd part of the Kleene’s theorem, If a language can be accepted by an RE then it can be accepted by a                         as well

►TG

►FA

►G and FA

►None of these

Question No: 37 ( Marks: 1 ) – Please choose one

If FA1 accepts no string and FA2 accepts many strings, then FA1 + FA2 will be equal to

►FA1

FA2

►May be both

►None of the given

Question No: 38 ( Marks: 1 ) – Please choose one

If r1 and r2 are regular expressions then which of the following is not regular expression.

►r1 = r2

►r1r2

►r1*

►r1 – r2

 Question No:39 ( Marks: 1 ) – Please choose one

Which of the following is not a word of language EQUAL?

►aaabbb

►abbbabaa

►abababa

►bbbaaa

Question No: 40 ( Marks: 1 ) – Please choose one

If S = {aa, bb}, then S* will not contain..

►aabbaa

►bbaabbbb

►aaabbb

►aabbbb

Question No: 41 ( Marks: 1 ) – Please choose one

One language can be represented by more than one RE” this statement is        

►False

►True

►Can’t be assumed

►None of these