# Thread: CS402 Theory of Automata Quiz No.3 Discussions and Solutions Spring 2014

1. ## CS402 Theory of Automata Quiz No.3 Discussions and Solutions Spring 2014

CS402 Theory of Automata Quiz No.3 Solutions Ideas Spring 2014 Due Date 24th July 2014

Question # 1 of 10 ( Start time: 04:12:20 PM ) Total Marks: 1
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

-----
Quiz Start Time: 04:12 PM Time Left 89
sec(s)

Question # 2 of 10 ( Start time: 04:13:44 PM ) Total Marks: 1
The product of two regular languages is __________.
Select correct option:

regular
infinite
non-regular
closure of a regular language

-------
Quiz Start Time: 04:12 PM Time Left 89
sec(s)

Question # 3 of 10 ( Start time: 04:14:36 PM ) Total Marks: 1
According to Myhill Nerode theorem, if L generates finite no. of classes then L is.......
Select correct option:

Finite
Infinite
Regular
Non regular

------

Quiz Start Time: 04:12 PM Time Left 90
sec(s)

Question # 4 of 10 ( Start time: 04:15:19 PM ) Total Marks: 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

-----

Quiz Start Time: 04:12 PM Time Left 89
sec(s)

Question # 5 of 10 ( Start time: 04:16:38 PM ) Total Marks: 1
In pref(Q in R) Q is …… to (than) R
Select correct option:

Equal
Not equal
Greater
Smaller

-------

Quiz Start Time: 04:12 PM Time Left 89
sec(s)

Question # 6 of 10 ( Start time: 04:17:14 PM ) Total Marks: 1
For language L defined over {a, b},then L partitions {a, b}* into …… classes
Select correct option:

Infinite
Finite
Distinct
Non distinct

-----

Quiz Start Time: 04:12 PM Time Left 88
sec(s)

Question # 7 of 10 ( Start time: 04:18:26 PM ) Total Marks: 1
Which of the following is not a true theorem?
Select correct option:

Decidability theorem
Equivalency theorem
Myhill Nerode theorem
Pseudo theorem

--------

Quiz Start Time: 04:12 PM Time Left 90
sec(s)

Question # 8 of 10 ( Start time: 04:19:37 PM ) Total Marks: 1
If a regular expression contains * then it _______ define an ________ language.
Select correct option:

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

------

Quiz Start Time: 04:12 PM Time Left 89
sec(s)

Question # 9 of 10 ( Start time: 04:20:48 PM ) Total Marks: 1
a^n b^n generates the ………… language
Select correct option:

regular
non regular
EQUAL and non regular
EQUAL and regular

---------

Quiz Start Time: 04:12 PM Time Left 87
sec(s)

Question # 10 of 10 ( Start time: 04:21:23 PM ) Total Marks: 1
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

2. 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
At least in one
None of the given options

Set of all palindromes over {a,b} is:
Regular
Regular and finite
Regular and infinite

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
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
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
At least in one
None of the given options

Set of all palindromes over {a,b} is:
Regular
Regular and finite
Regular and infinite

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

##### Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•
-: Vuhelp Disclaimer :-
None of the files shown here are hosted or transmitted by this server. The links are provided solely by this site's users. The administrator's or staff of Vuhelp.net cannot be held responsible for what its users post, or any other actions of its users. You may not use this site to distribute or download any material when you do not have the legal rights to do so. It is your own responsibility to adhere to these terms. If you have any doubts about legality of content or you have any suspicions, feel free to contact us.
Online Education | JhelumSoft