**AUTOMATA THEORY MCQS**

(1) For a given input, it provides the
compliment of Boolean AND output.

NAND box (NOT AND)

DELAY box

OR box

AND box

(2) It
delays the transmission of signal along the wire by one step (clock pulse).

NAND box (NOT AND)

DELAY box

OR box

AND box

(3) For
the given input, it provides the Boolean OR output

NAND box (NOT AND)

DELAY box

OR box

AND box

(4) For
the given input, AND box provides the Boolean AND output.

True

False

(5) The
current in the wire is indicated by 1 and 0 indicates the absence of the current.

True

False

(6) Any
language that can not be expressed by a RE is said to be regular language.

True

False

(7) If
L1 and L2 are regular languages is/are also regular language(s).

L1
+ L2

L1L2

L1

All of above

(8) Let
L be a language defined over an alphabet Î£, then the language of strings,
defined over Î£, not belonging to L, is called Complement of the language L, denoted by Lc or L’.

True False

(9) To
describe the complement of a language, it is very important to describe the
----------- of that language over which the language is defined.

Alphabet

Regular
Expression

String

Word

(10) For
a certain language L, the complement of Lc is the given language L

*i.e.*(Lc)c = Lc
True

False

(11) If L is a regular language then, ---------
is also a regular language.

Lm

Ls

Lx

Lc

(12) Converting each of the final states of F to
non-final states and old non-final states of F to final states, FA thus
obtained will reject every string belonging to L and will accept every string,
defined over Î£, not belonging to L. is called

Transition Graph of L

Regular expression of L

Complement of L

Finite Automata of L

(13) If
L1 and L2 are two regular languages, then L1 U L2 is not a regular.

True

False

(14) De-Morgan's
law for sets is expressed by,

(15) If L1 and L2 are regular languages, then
these can be expressed by the corresponding FAs.

True

False

(16) L=
language of words containing even number of a’s. Regular
Expression is

(a+b)aa(a+b)

(b+aba)

a+bbaaba

(a+b)ab(a+b)

(17) The regular expression defining the
language L1 U
L2 can be obtained, converting and reducing the
previous ------------- into a ------------ as after eliminating states.

GTG, TG

FA, GTG

FA, TG

TG, RE

(18) The
language that can be expressed by any regular expression is called a Non regular language.

True

False

(19) The languages -------------- are the
examples of non regular languages.

PALINDROME and PRIME

PALINDROME
and EVEN-EVEN

EVEN-EVEN
and PRIME

FACTORIAL
and SQURE

(20) Let
L be any infinite regular language, defined over an alphabet Î£
then
there exist three strings x, y and z belonging to Î£such that all the
strings of the form XY^ n Z for n=1,2,3, … are the words in L. called.

Complement
of L

Pumping Lemma

Kleene’s
theorem

None
in given

(21)
Languages are proved to be regular or non regular
using pumping lemma.

True

False

(22) -------------------
is obviously infinite language.

EQUAL-EQUAL

EVEN-EVEN

PALINDROME

FACTORIAL

(23) If, two strings x
and y, defined over Î£, are run over an FA accepting
the language L, then x and y are said to belong to the same class if they end
in the same state, no matter that state is final or not.

True

False

Myhill
Nerode theorem is consisting of the followings,

L
partitions Î£into distinct classes.

If
L is regular then, L generates finite number of classes.

If
L generates finite number of classes then L is regular.

All of above

The
language Q is said to be quotient of two regular
languages P
and R, denoted by--- if PQ=R.

R=Q/P

Q=R/P

Q=P/R

P=R/Q

If
two languages R and Q are given, then the
prefixes of Q in R denoted
by Pref(Q in R).

True

False

(27) Let Q = {aa,
abaaabb, bbaaaaa, bbbbbbbbbb} and R = {b, bbbb, bbbaaa, bbbaaaaa}

Pref (Q in R) is equal
to,

{b,bbba,bbbaaa}

{b,bba,bbaaa}

{ab,bba,bbbaa}

{b,bba,bbba}

If
R is regular language and Q is any language (regular/
non
regular), then Pref (Q in R) is ---------.

Non-regular

Equal

Regular

Infinite

"CFG" stands for _________

Context Free Graph

Context Free Grammar

Context Finite Graph

Context Finite Grammar

(29) ___________
states are called the halt states.

ACCEPT and REJECT

ACCEPT and READ

ACCEPT AND START

ACCEPT AND WRITE

(30) The
part of an FA, where the input string is placed before it is run, is called
_______

State

Transition

Input Tape

Output Tape

In new format of an FA (discussed in
lecture 37), This state is like dead-end non final state

ACCEPT

REJECT

STATR

READ

For language L defined over {a, b}, then L
partitions {a, b}into …… classes

Infinite

Finite

Distinct

Non-distinct

The major problem in the earliest computers
was

To store the contents in the registers

To display mathematical formulae

To load the contents from the registers

To calculate the mathematical formula

Between the two consecutive joints on a
path

One character can be pushed and one
character can be popped

Any no. of characters can be pushed and one character can be popped

One character can be pushed and any no. of
characters can be popped

Any no. of characters can be pushed and any
no. of characters can be popped

(35) In
pumping lemma theorem (x y^n z) the range of n is

n=1, 2, 3, 4……….

n=0, 1, 2, 3, 4……….

n=…….-3,-2,-1, 0, 1, 2, 3, 4……

n=…….-3,-2,-1, 1, 2, 3, 4……

(36) The
PDA is called non-deterministic PDA when there are more than one out going
edges from……… state

START or READ

POP or REJECT

READ or POP

PUSH or POP

Identify the TRUE statement:

A PDA is non-deterministic, if there are
more than one READ states in PDA

A PDA is never non-deterministic

Like TG, A PDA can also be non-deterministic

A PDA is non-deterministic, if there are
more than one REJECT states in PDA

There
is a problem in deciding whether a state of FA should be marked or not when the
language Q is infinite.

True

False

If
an effectively solvable problem has answered in yes or no, then this solution
is called ---------

Decision procedure

Decision
method

Decision
problem

Decision
making

The
following problem(s) ------------- is/are called decidable problem(s).

The
two regular expressions define the same language

The
two FAs are equivalent

Both a and b

None
of given

To
examine whether a certain FA accepts any words, it is required to seek the
paths from ------- state.

Final
to initial

Final
to final

Initial to final

Initial
to initial

The
high level language is converted into assembly language codes by a program
called compiler.

TRUE

FALSE

Grammatical
rules which involve the meaning of words are called ---------------

Semantics

Syntactic

Both a and b

None of given

Grammatical
rules which do not involve the meaning of words are called ---------------

Semantics

Syntactic

Both a and b

None of given

The
symbols that can’t be replaced by anything are called -----------------

Productions

Terminals

Non-terminals

All
of above

The
symbols that must be replaced by other things are called __________

Productions

Terminals

Non-terminals

None
of given

(47) The grammatical rules are often
called_____________

Productions

Terminals

Non-terminals

None
of given

The
terminals are designated by ________ letters, while the non-terminals are
designated by ________ letters.

Capital,
bold

Small, capital

Capital,
small

Small,
bold

The
language generated by __________ is called Context Free Language (CFL).

FA

TG

CFG

TGT

(49) Î£ =
{a,b} Productions S→XaaX X→aX X→bX X→Î›

This grammar defines the language
expressed by___________

(a+b)aa(a+b)

(a+b)a(a+b)a

(a+b)aa(a+b)aa

(a+b)aba+b)

(50) S →
aXb|b XaX → aX|bX|Î›
The given CFG generates the language in English __________

Beginning and
ending in different letters

Beginning and ending in same letter

Having even-even language

None of given

(51) The CFG is not said
to be ambiguous if there exists atleast one word of its language that can be
generated by the different production trees,

TRUE

FALSE

The
language generated by that CFG is regular
if _________

No
terminal → semi word

No
terminal → word

Both a and b

None
of given

The
production of the form no terminal → Î› is said to be null
production.

TRUE

FALSE

(54) A production is
called null able production if it is of the form N → Î›

TRUE

FALSE

(55) The productions of the form nonterminal →
one
nonterminal, is called _________

Null
production

Unit production

Null able production

None of given

(56) CNF is
stands for

Context Normal Form

Complete Normal Form

Chomsky Normal
Form

Compared Null Form

Proof(Kleene’s Theorem Part II)

If a
TG has more than one start states, then

Introduce the new start state

Eliminate the old start state

Replace the old start state with final state

Replace the old final state with new start state

Question # 2

While finding RE corresponding to TG, we
connect the new start state to the old start state by the transition labeled by

Select correct option:

a

b

null string

None of the given options

Select correct option:

a

b

null string

None of the given options

Question # 3 of 10 ( Start time: 05:49:03
PM ) Total Marks: 1

Which of the following regular expression represents same language? a. (a+ab)b. (ba+a)c. a(aab)d. (ab)

Which of the following regular expression represents same language? a. (a+ab)b. (ba+a)c. a(aab)d. (ab)

a+b)a(a+b)b(a+b)+ (a+b)b(a+b)a(a+b).

{ x}, { x}+, {a+b}

Select correct option:

a and b

a and c

c and d

Question # 4 of 10 ( Start time: 05:50:32
PM ) Total Marks: 1

(a+ b)= (a + b)this expression is __________

Select correct option:

True

False

(a+ b)= (a + b)this expression is __________

Select correct option:

True

False

Question # 5 of 10 ( Start time: 05:51:30
PM ) Total Marks: 1

Let FA3 be an FA corresponding to FA1+FA2, then the initial state of FA3 must correspond to the initial state of

Select correct option:

FA1 only

FA2 only

FA1 or FA2

FA1 and FA2

Let FA3 be an FA corresponding to FA1+FA2, then the initial state of FA3 must correspond to the initial state of

Select correct option:

FA1 only

FA2 only

FA1 or FA2

FA1 and FA2

Question # 6 of 10 ( Start time: 05:53:01
PM ) Total Marks: 1

Which of the following statement is NOT true about TG?

Select correct option:

There exists exactly one path for certain string

There may exist more than one paths for certain string

There may exist no path for certain string

There may be no final state

Which of the following statement is NOT true about TG?

Select correct option:

There exists exactly one path for certain string

There may exist more than one paths for certain string

There may exist no path for certain string

There may be no final state

Question # 7 of 10 ( Start time: 05:54:06
PM ) Total Marks: 1

Kleene’s theorem states

Select correct option:

All representations of a regular language are equivalent.

All representations of a context free language are equivalent.

All representations of a recursive language are equivalent

Finite Automata are less powerful than Pushdown Automata.

Kleene’s theorem states

Select correct option:

All representations of a regular language are equivalent.

All representations of a context free language are equivalent.

All representations of a recursive language are equivalent

Finite Automata are less powerful than Pushdown Automata.

Question # 8 of 10 (Start time: 05:55:36
PM) Total Marks: 1

What do automata mean?

Select correct option:

Something done manually

Something done automatically

What do automata mean?

Select correct option:

Something done manually

Something done automatically

Question # 9 of 10 ( Start time: 05:56:51
PM ) Total Marks: 1

A language accepted by an FA is also accepted by

Select correct option:

TG only

GTG only

RE only

All of the given

A language accepted by an FA is also accepted by

Select correct option:

TG only

GTG only

RE only

All of the given

Question # 10 of 10 ( Start time: 05:58:16
PM ) Total Marks: 1

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

Select correct option:

(r1)(r2)

(r1 + r2)

(r2)(r1)

(r1)

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

Select correct option:

(r1)(r2)

(r1 + r2)

(r2)(r1)

(r1)

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

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

► (r1)(r2)

► (r1 + r2)

► (r2)(r1)

► (r1)

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

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

► True

► False

► Some times true & sometimes false

► None of these

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

Who did not invent the Turing machine?

► Alan Turing

► A. M. Turing

► Turing

► None of these

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

Which statement is true?

► The tape of
turing machine is infinite.

► The tape of turing machine is finite.

► The tape of turing machine is infinite when the language is regular

► The tape of turing machine is finite when the language is nonregular.

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

A regular language:

► Must be finite

► Must be infinite

► Can be finite or infinite

► Must be finite and cannot be infinite

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

Every regular expression can be expressed as CFG but every CFG
cannot be expressed as a regular expression. This statement is:

► Depends on the language

► None of the given options

► True

► False

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

Above given FA corresponds RE r. then FA
corresponding to rwill be

This statement is

► True

► False

► Depends on language

► None of these

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

Consider the language L of strings, defined over Î£ = {a,b}, ending
in a

► There are finite many classes generated by L, so L is regular

►
There
are infinite many classes generated by L, so L is regular

► There are finite many classes generated by L, so L is non-regular

► There are infinite many classes generated by L, so L is non-regular

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

Above given TG has _____________ RE.

► (aa+aa+(ab+ab)(aa+ab)(ab+ba))

►
(aa+bb+(ab+ba)(aa+bb)(ab+ba))

► (aa+bb+(ab+ba)(aa+bb)(ab+ba))

► None of these

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

The word ‘formal’ in formal languages means

► The symbols used
have well defined meaning

► They are unnecessary, in reality

► Only the form of the string of symbols is significant

► None of these

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

Let A = {0, 1}. The number of possible strings of length ‘n’ that
can be formed by the elements of the set A is

► n!

► n

^{2}
► n

^{m}
► 2

^{n}
Question
No: 12 ( Marks: 1 ) - Please choose one

Choose the correct statement.

► A Mealy machine generates no language as
such

► A Moore machine generates no language as such

► A Mealy machine has no terminal state

► All of these

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

TM is more powerful than FSM because

► The tape movement is confined to one direction

► It has no finite state control

► It has the capability to remember arbitrary long sequences of input
symbols

► None of these

Question
No: 14 ( 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: 15 ( Marks: 1 ) - Please choose one

Like TG, a PDA can also be non-deterministic

► True

► False

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

The above machine is a/anTG ___________

► Finite Automata

► Turing machine

► FA

► TG

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

The language of all words (made up of a’s and b’s) with at least
two a’s can not be described by the regular expression.

►
a(a+b)a(a+b)(a+b)ab

► (a+b)aba(a+b)

► baba(a+b)

► none of these

Question
No: 18 ( 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 State

► Waste Basket

► Davey John Locker

► All of these

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

If L is a regular language then, L

^{c}is also a _____ language.
► Regular

► Non-regular

► Regular but finite

► None of the given

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

In CFG, the symbols that can’t be replaced by anything are
called___

► Terminal

► Non-Terminal

► Production

► All of given

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

Which of the following is NOT a regular language?

► String of 0’s whose length is a perfect squere

► Set of all palindromes made up of 0’s and 1’s

► String of 0’s whose length is a prime number

► All of the given options

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

Choose the incorrect (FALSE)
statement.

► A Mealy machine generates no language as such

► A Mealy machine has no terminal state

► For a given input
string, length of the output string generated by a Moore machine is not more than the length of
the output string generated by that of a Mealy machine

► All of these

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

Pumping lemma is generally used to prove that:

► A given language is infinite

► A given language is not regular

► Whether two given regular expressions of a regular language are
equivalent or not

► None of these

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

Which of the following is a regular language?

► String of odd number of zeroes

► Set of all palindromes made up of 0’s and 1’s

► String of 0’s whose length is a prime
number

► All of these

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

Choose the incorrect statement:

► (a+b)aa(a+b)generates Regular language.

► A language consisting of all strings over ∑={a,b} having equal number
of a’s and b’s is a regular language

► Every language that can be expressed by FA can also be expressed by RE

► None of these

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

Left hand side of a production in CFG consists of:

► One terminal

► More than one terminal

► One non-terminal

► Terminals and
non-terminals