# CS402 Theory of Automata Quiz 2 Fall 2012

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

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

While determining regular expression for a given FA, it is _________ to write its regular expression.

Always possible easily
Sometime impossible
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
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
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
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
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
5
6

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

Equal
Not equal
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
Finite solution
None of the given option