Posts: 323
Threads: 241
Joined: Oct 2012
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
Answer: 2
-----
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
Answer: 1
-------
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
Answer:3
------
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
Answer:2
-----
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
Answer: 2
-------
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
Answer: 3
-----
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
Answer: 4
--------
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
Answer: 2
------
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
Answer: 2
---------
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
Answer: 4
Posts: 323
Threads: 241
Joined: Oct 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 -= 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
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
