CS402 Quiz Solution If the intersection of two regular languages is regular then the complement of the intersection of these two languages i
CS402 Quiz Solution
If the intersection of two regular languages is regular then the complement of the intersection of these two languages is __________.
Regular
The language of all strings partition ∑* into ___________ class(es).
Two
The language of all strings not beginning with ‘b’ partitions ∑* into ___________distinct classes.
Two
If Q = {xx, xyxxxy }, and R = {xyxyxyxxyy, xyxyyyxx} then Pref( Q in R) = ____________
xyxyyy
A language ending with ‘b’ partitions ∑* into ___________distinct classes.
Three
If R is regular language and Q is any language (regular/ non-regular), then Pref( _______in _______) is regular.
Q,R
The reverse of the string sbfsbb over { sb, f, b }
Sb, f, sb, b
Bsbfsb
The basic approach of Myhill Nerode theorem is similar to the concept of:
concatenation of FAs
If there is no final state of two FAs then their ______ also have no _____ state
union, final
If an FA has N states then it must accept the word of length
N
For a machine with N number of sta., the total number of strings to be tested, defined over an alphabet of m letters, is
mN +mN+1+ mN,-2 ,m2N-1
Which of the following is not a true theorem?
Pseudo theorem
The language "PRIME” is an example of language.
non regular
The product of two regular languages is
Regular
One language can have _______ CFG(s).
More than one
Which of the following is a non-regular language?
Prime
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.
accept no
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.
Impossible
A problem that has decision procedure is called problem.
Decidable problem
Which one of the following languages is a non regular language?
Palindrome
Using Myhill Nerode theorem we partition sigma star into distinct
Classes
In pumping lemma theorem (x y"n z) the range of n is
n=1. 2, 3, 4.......
The values of input (say a & b) do not remain same in one cycle due to
NOT gate
The operators like (*" +) in the parse tree are considered as
Terminals
Even-Even language partitions ∑* into _________ distinct classes.
Four
The strings or words which do not belong to a language are called _________ of that language.
Complement
The production S —> SS lalbl^ can be expressed by Regular expression
(a+b)+
if L1 and L2 are two regular languages. then they expressed by FAs.
can be
The grammatical rules which involve meaning of words are called
Semantics
Set of all palindromes over (a,b) is:
Regular and finite
The language of all strings not beginning with partitions “b" into distinct classes.
Two
The CFG is said to be ambiguous if there exist at least one word of its language that can be generated by production trees.
More than one
The CFG S —> aSb|abl^ is used to express the language
Palindrome
A non regular language can be represented by
None of the given options
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.
Impossible
In polish notation, (o-o-o) is the abbreviation of _________.
Operator - Operand – Operand
If an FA has N states then it must accept the word of length
N
Using Myhill Nerode theorem we partition sigma star into distinct __________.
classes
If a language is regular it must generate ____________ number of distinct classes.
finite
If L1 and L2 are regular languages then which statement is NOT true?
L1/L2 is always regular
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.
accept no
A problem that has decision procedure is called _________ problem.
decidable
If L1 and L2 are two regular languages, then they _______ expressed by FAs.
can be
A language that can be expressed by RE, is said to be a _______ language.
regular
The values of input (say a & b) do not remain same in one cycle due to
NOT gate
Prime is a ______________ language.
non-regular
If an effectively solvable problem has answer in YES or NO, then the solution is called _________.
decision procedure
To write the expression from the tree, it is required to traverse from ___________.
Left side of the tree
If there is no final state of two FAs then their ______ also have no _____ state
union,final
In CFG, symbols that cannot be replaced by anything are called __________.
terminals
Finite Automaton (FA) must have __________ number of states while a language has _________ words.
finite, infinite
The language “PRIME” is an example of ________ language.
non regular
Using Myhill Nerode theorem we partition sigma star into distinct __________.
classes
Even-Even language partitions ∑* into ___________ distinct classes.
four
What will be the 9’s complement of the number 872?
127
In pref(Q in R), Q is _______ to/than R.
Not equal
There is at least one production in CFG that has one _________ on its left side.
Non terminal
In pumping lemma theorem (x y^n z) the range of n is
n=1, 2, 3, 4……….
A language ending with ‘b’ partitions ∑* into ___________distinct classes.
three
The operators like (* , +) in the parse tree are considered as ________.
terminals
For a machine with N number of states, the total number of strings to be tested, defined over an alphabet of m letters, is _____________.
mN +mN+1+ mN+2 +… +m2N-1
In a CFG, the non-terminals are denoted by _________.
Capital letters
If an FA accepts a word then there must exist a path from __________.
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.
finite
Which of the following is pumped to generate further strings in the definition of Pumping Lemma?
y
The complement of a regular language is also __________.
regular
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
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
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
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
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
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
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
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
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
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
Question # 3 of 10 ( Start time: 06:25:04 PM ) Total Marks: 1
If r1 and r2 are regular expressions then which of the following is not regular expression
r1 + r2
r1 r2
r1*
r1 – r2
Question # 4 of 10 ( Start time: 06:25:47 PM ) Total Marks: 1
Kleene star closure can be defined
Over any set of string
Over specific type of string
Question # 5 of 10 ( Start time: 06:26:29 PM ) Total Marks: 1
Which of following string(s) belongs to the language of the regular expression (aa*b)*?
baabab
abbbaa
aaaaaa
aabaab
Question # 6 of 10 ( Start time: 06:27:05 PM ) Total Marks: 1
According to theory of automata there are _________ types of languages
Select correct option:
One
Two
Three
Four
Question # 7 of 10 ( Start time: 06:27:38 PM ) Total Marks: 1
If S = {aa, bb}, then S* will not contain
aabbaa
bbaabbbb
aaabbb
aabbbb
Question # 8 of 10 ( Start time: 06:28:25 PM ) Total Marks: 1
Every non deterministic Finite Automata can be converted into
Regular Expression
Deterministic Finite Automata
Trasition Graph
All of the given options
Question # 9 of 10 ( Start time: 06:29:38 PM ) Total Marks: 1
The states in which there is no way to leave after entry are called
Davey John Lockers
Dead States
Waste Baskets
All of the given options
Question # 10 of 10 ( Start time: 06:30:18 PM ) Total Marks: 1
(a* + b*)* = (a + b)* this expression is _________
True
False
Question # 1 of 10 ( Start time: 06:34:10 PM ) Total Marks: 1
What is false about the PALINDROME LANGUAGE?
Every word is reverse of itself.
It is an infinite language.
FA can be build for it.
None of the given optio
Question # 2 of 10 ( Start time: 06:35:40 PM ) Total Marks: 1
FA is also called
TG
GTG
NFA
DFA
Question # 3 of 10 ( Start time: 06:36:21 PM ) Total Marks: 1
Kleene star closure can be defined
Over any set of string
Over specific type of string
Question # 4 of 10 ( Start time: 06:36:35 PM ) Total Marks: 1
[(a + b)(a + b)]*, given RE cannot generate the string ________
abbaabab
abbbaa
bbbbbb
abbbaaaaa
Question # 5 of 10 ( Start time: 06:37:19 PM ) Total Marks: 1
In an FA, when there is no path starting from initial state and ending in final state then that FA
accept null string
accept all strings
accept all non empty strings
does not accept any string
Question # 6 of 10 ( Start time: 06:38:22 PM ) Total Marks: 1
While finding RE corresponding to TG, we connect the new start state to the old start state by the transition labeled by
a
b
null string
None of the given options
Question # 7 of 10 ( Start time: 06:39:30 PM ) Total Marks: 1
According to theory of automata there are _________ types of languages
One
Two
Three
Four
Question # 8 of 10 ( Start time: 06:39:43 PM ) Total Marks: 1
While finding RE corresponding to TG, If TG has more than one final state then
Introduce the new final state
Eliminate the old final state
Replace the old final state with start state
Replace the old final state with new start state
Question# 9 of 10 ( Start time: 06:40:51 PM ) Total Marks: 1
The states in which there is no way to leave after entry are called
Select correct option:
Davey John Lockers
Dead States
Waste Baskets
All of the given options
Question # 10 of 10 ( Start time: 06:41:07 PM ) Total Marks: 1
What is false about the term alphabet?
It is a finite set of symbols.
It is usually denoted by Greek letter sigma
It can be an empty set.
Strings are made up of its elemen
COMMENTS