automata theory multiple choice questions mcq with answers

 automata theory multiple choice questions mcq with answers 

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

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)

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

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

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

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.

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

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

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)