# Theory of Automata

## 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

► Depends on NFA

#### 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

► 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

► 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

► Davey John Lockers

#### 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

►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+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.

►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

►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

#### 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

►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

►bbbaaa

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

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

►aabbaa

►bbaabbbb

►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

SHARE
Previous articleFundamental of Algorithms
Next articleData Communication