CS402 Theory of Automata Online Solved Quizzes/MCQ's File No 2

Closure of an FA is same as concatenation of an FA with itself?
True
False

In Closure of an FA the initial state of a required FA is

Initial state of another FA
Final State of another FA
Final state as well of the same FA
None of the Given

NFA is a TG as well?
True
False

Considering FA1 and FA2 having 2 states each. Now FA1+FA2 can have maximum number of states.
2
3
It will be more than 3.
None of them

A _________ is the one for which every input string has a unique path through the

machine.

deterministic PDA

nondeterministic PDA

PUSHDOWN store

Input Tape

Quiz : 07:08 88

CS402 Question # 5 of 10

In the null production N --> ^ , N is a

Terminal

Non terminal

Word

None of the given options

Quiz : 07:08 88

CS402 Question # 6 of 10

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

Quiz : 07:08 88

CS402 Question # 7 of 10

In polish notation, (o-o-o) is the abbreviation of………?

Operand - Operator – Operand

Operand - Operand- Operator

Operator -Operand – Operand

Operand -Operand – Operand

Which of the following is NOT a regular language?
Select correct option:
String of 0’s whose length is a perfect square
Set of all palindromes made up of 0’s and 1’s -= Answer
String of 0’s whose length is a prime number
All of the given options

If there is no final state of two FAs then their ____ also have no ___ state
Select correct option:
initial, union
final, union
union, final -= Answer
union, initial

1.which path sequence follows the rules of "conversion form" of "PDA"

READ -> POP -> POP

2. In a CFG the nonterminal that occurs first from the left in the working string, is said to be ________

Least Significant nonterminal
Most Significant nonterminal
Left most nonterminal
Left most nonterminal

3. The PDA which is in the conversion form can be supposed to be the _________ with path segments in between, similar to a TG.

Set of joints
Set of Forks
Set of Plugs
None of given options

Incase of Myhill Nerode theorem, if a language L partitions sigma star into distinct classes and L is also regular then L generates_________ number of classes.
Select correct option:
infinite
specified
finite -= Answer
odd

For a machine with N number of states, the total number of strings to be tested, defined over an alphabet of m letters, is___________.
Select correct option:
Nm +Nm+1+ N m+2 +… + N2m-1
mN +mN+1+ mN+2 +… +m2N-1 -= Answer
Nm
mN

4. The CFG is said to be ambiguous if there exist at least one word of its language that can be generated by the ………… production trees

One
Two
More than one
At most one

If (L1 ^?L2c ) u?( L1C ^ L2) is regular language that accepts the words which are in L1 but not in L2 or else in L2 but not in L1 . The corresponding FA cannot accept any word which is in _______ L1 and L2.
Not both
Both -= Answer
At least in one
None of the given options

Set of all palindromes over {a,b} is:
Regular
Regular and finite
Regular and infinite
Non-regular-= Answer

While determining regular expression for a given FA, it is _________ to write its regular expression.
Always possible easily
Sometime impossible -= Answer
always impossible
None of the given options

Incase of Myhill Nerode theorem, if a language L partitions sigma star into distinct classes and L is also regular then L generates_________ number of classes.
Select correct option:
infinite
specified
finite -= Answer
odd

Which of the following is NOT a regular language?
Select correct option:
String of 0’s whose length is a perfect square
Set of all palindromes made up of 0’s and 1’s -= Answer
String of 0’s whose length is a prime number
All of the given options

If there is no final state of two FAs then their ____ also have no ___ state
Select correct option:
initial, union
final, union
union, final -= Answer
union, initial

For a machine with N number of states, the total number of strings to be tested, defined over an alphabet of m letters, is___________.
Select correct option:
Nm +Nm+1+ N m+2 +… + N2m-1
mN +mN+1+ mN+2 +… +m2N-1 -= Answer
Nm
mN

In the context of Myhill Nerode theorem, for even-even language sigma star can be partitioned into________ number of classes.
Select correct option:
3
4 -= Answer
5
6

In pref(Q in R) Q is …… to (than) R
Select correct option:
Equal
Not equal -= Answer
Greater
Smaller

If an effectively solvable problem has answer in yes or no, then this solution is called_______.
Select correct option:
Infinite problem
decision procedure -= Answer
Finite solution
None of the given option

If (L1 ^?L2c ) u?( L1C ^ L2) is regular language that accepts the words which are in L1 but not in L2 or else in L2 but not in L1 . The corresponding FA cannot accept any word which is in _______ L1 and L2.
Not both
Both -= Answer
At least in one
None of the given options

Set of all palindromes over {a,b} is:
Regular
Regular and finite
Regular and infinite
Non-regular-= Answer

While determining regular expression for a given FA, it is _________ to write its regular expression.
Always possible easily
Sometime impossible -= Answer
always impossible
None of the given options

NFA helps to eliminate at certain state of an FA
Loop
FA
NFA
String

It is possible to convert an FA into NFA?

True
False

NFA helps to eliminate loop at certain state of an FA in this process loop is converted into

String
Circuit

If an effectively solvable problem has answer in yes or no, then this solution is called_______.
Select correct option:
Infinite problem
decision procedure -= Answer
Finite solution
None of the given option

5. Identify the FALSE statement about following CFG: S -> SB|AB A -> CC B -> b C -> a

CFG generates NULL string
CFG is not in CNF
CFG has 8 Nonterminals
All of the given options

6. In a STACK:

The element PUSHed first is POPed first
The element PUSHed first is POPed in the last
The element PUSHed in last is POPed in last
None of given options

7. Consider the following CFG: (NOTE: ^ means NULL) S->a|Xb|aYa X->Y|^ Y->b|X Which Nonterminal(s) is/are NOT nullable

S,X and Y

8. Consider the Following CFG: (NOTE: ^ means NULL) S->Xa X->aX|bX|^ above given CFG can be represented by RE _________

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

9. If a CFG has only productions of the form nonterminal -> string of two nonterminals or nonterminal -> one terminal then the CFG is said to be in _________

PDA form
Chomsky Normal Form (CNF)
NULL able form
Unit production form

10. The structure given below is called _________ S -> aA|bB A -> aS|a B -> bS|b

RE
TG
CFG
PDA

In large FA with thousands of states and millions of directed edges, without an effective procedure it is ________ to find a path from initial to final state.
Select correct option:
Always easy
Impossible
may be good
always impossible

For language L defined over {a, b},then L partitions {a, b}* into …… classes
Select correct option:
Infinite
Finite
Distinct
Non distinct

If a regular expression contains * then it _______ define an ________ language.
Select correct option:
always, finite
may, infinite
always, infinite
None of the given options

In pref(Q in R) Q is …… to (than) R
Select correct option:
Equal
Not equal
Greater
Smaller

If the intersection of two regular languages is regular then the complement of the intersection of these two languages is also regular
Select correct option:
True
False

If an effectively solvable problem has answer in yes or no, then this solution is called _________.
Select correct option:
Infinite problem
decision procedure
Finite solution
None of the given option

For a machine with N number of states, the total number of strings to be tested, defined over an alphabet of m letters, is _____________.
Select correct option:
Nm +Nm+1+ N m+2 +… + N2m-1
mN +mN+1+ mN+2 +… +m2N-1
Nm
mN

If the FA has N states, then test the words of length less than N. If no word is accepted by this FA, then it will _________ word/words.
Select correct option:
accept all
accept no
accept some
reject no
M Shahbaz:
If an FA has N state then it must accept the word of length
Select correct option:
N-1
N+1
N
2N

The values of input (say a & b) does not remain same in one cycle due to
Select correct option:
NAND gate
Clock pulse
OR gate
NOT gate

According to Myhill Nerode theorem, if L generates finite no. of classes then L is.......
Select correct option:
Finite
Infinite
Regular
Non regular

If a regular expression contains * then it _______ define an ________ language.
Select correct option:
always, finite
may, infinite
always, infinite
None of the given options

The reverse of the string sbfsbb over { sb, f, b }
Select correct option:
bbsfbs
bsbfsb
sbbfsb
bsfbsb

The strings or words which do not belong to a language is called…………. of that language
Select correct option:
Intersection
Union
Complement
Quotient

An FA has same initial and _____ state, then it means that it has no _______ state.
Select correct option:

initial, final
final, initial
initial, initial
none of the given options

Answer: 2

------

The product of two regular languages is __________.
Select correct option:

regular
infinite
non-regular
closure of a regular language

Answer: 1
-------

Two languages are said to belong to same class if they end in the same state when they run over an FA, that state
Select correct option:

Must be final state
May be final state or not
May be start state or not
None of the given option

Answer:2
-----

In the context of Myhill Nerode theorem, for even-even language sigma star can be partitioned into________ number of classes.
Select correct option:
3
4 -= Answer
5
6

In pref(Q in R) Q is …… to (than) R
Select correct option:
Equal
Not equal -= Answer
Greater
Smaller

In pref(Q in R) Q is …… to (than) R
Select correct option:

Equal
Not equal
Greater
Smaller

Answer: 2

-------

Closure of an FA, is same as ___________ of an FA with itself, except
that the initial state of the required FA is a final state as well.
Select correct option:
Union
Sum
Concatenation (answer)

Considering FA1 and FA2 having 2 states each. Now FA1+FA2 can have maximum ______________ number of states.2
3
more than 3.
none of them

If a regular expression contains * then it _______ define an ________ language.
Select correct option:

always, finite
may, infinite
always, infinite
None of the given options

Answer: 2

------

a^n b^n generates the ………… language
Select correct option:

regular
non regular
EQUAL and non regular
EQUAL and regular

Answer: 2

---------

a^n b^n generates the ………… language
Select correct option:
regular
non regular
EQUAL and non regular
EQUAL and regular
Incase of Myhill Nerode theorem, if a language L partitions sigma star into distinct classes and L is also regular then L generates ___________ number of classes.
Select correct option:
infinite
specified
finite
odd

Closure of an FA, is same as of an FA with itself, except
that the initial state of the required FA is a final state as well.

Union
Sum
Concatenation (answer)
Intersection
If R is a regular language and L is some language, and L U R is a regular language, then L must be a regular language.
True
False

If R is a regular language and L is some language, and L U R is a RE then L must be a
Concatenation
Regular Language

There a unique path for each string in NFA?
Must be
May be
Should be
May not be

To examine whether a certain FA accepts any words, it is required to seek the paths _______ state.
Select correct option:

from final to initial
from initial to initial back
from final to back final
from initial to final

Answer: 4
If a Language is accepted by an FA then there exists a TG accepting the language?
True
False

It is clear by the definition of NFA that a string is supposed to be accepted if there exist at least successful path
Two
One
More than one
More than two

Can NFA and FA be equivalent?
Yes
No

Can be considered as intermediate structure between FA and TG

GTG
NFA

Artificial Intelligence is important example of

FA
GTG
TG
NFA

For language L defined over {a, b},then L partitions {a, b}* into …… classes
Select correct option:

Infinite
Finite
Distinct
Non distinct

Answer: 3
-----

According to Myhill Nerode theorem, if L generates finite no. of classes then L is.......
Select correct option:

Finite
Infinite
Regular
Non regular

Answer:3
------

Which of the following is not a true theorem?
Select correct option:

Decidability theorem
Equivalency theorem
Myhill Nerode theorem
Pseudo theorem

Answer: 4

--------

1. Two languages are said to belong to same class if they C when they run over an FA, that state (May be final State or not).

2. One language can have ……… CFG(s) (At least one)

3. If an FA has N state then it must accept the word of length (n+1)

4. In pumping lemma theorem (x y^n z) the range of n is (1,2,3,4,………)

5. For a non regular language there exist …… FA (NO)

6. If the intersection of two regular languages is regular then the complement of the intersection of these two languages is also regular (True)

7. According to Myhill Nerode theorem, if L generates finite no. of classes then L is.......(Regular)

8. The language generated by the CFG is called the language ……by the CFG (Produced)

9. If L1 and L2 are regular languages then which statement is NOT true? (L1/L2 is always regular)

10. The values of input (say a & b) does not remain same in one cycle due to (clock pulse)

11. The reverse of the string sbfsbb over { sb, f, b } (bsbfsb)

12. In CFG, the symbols that cannot be replaced by anything are called Terminals

13. a^n b^n generates the ………… language (Non regular languages)

14. The production S --> SS | a | b | ^ can be expressed by RE (a+b)+

Any word generated by given CFG can also be expressed by (Syntax tree or Generation
tree or Derivation tree as well)

15. Set of all palindromes over {a,b}is regular (false)

16. The grammatical rules which involves meaning of words are called: (semantic)

17. An FA has same initial and final state, then it means that it has no final state. (false)

18. The same non terminals can be written in single line if they have more than one..........(Productions)

19. In pref(Q in R) Q is …… to (than) R (Q is not equal to R)

20. The complement of a regular language is also a regular (True)

21. There is at least one production that has one........on its left side. (None Terminal)

22. For language L defined over {a, b},then L partitions {a, b}* into …… classes (Distinct)

CS402 Theory of Automata Online Solved Quizzes/MCQ's File No 2

Post a Comment

Contact form