Every TG is an FA
Select correct option:
True
False Correct
Let FA3 be an FA corresponding to FA1+FA2, then the initial state of FA3 must correspond to the initial state of
Select correct option:
FA2 only
FA1 or FA2 Correct
FA1* and FA2*
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
Quiz : 07:08 88
CS402 Question # 9 of 10
The input string is placed, before it runs, in
Stack
Memory
Tape
Ram
Quiz : 07:08 89
CS402 Question # 10 of 10
Which of the following states is not part of PDA
START
ACCEPT
WRTITE
REJECT
Kleene’s theorem states
Select correct option:
All representations of a regular language are equivalent. Correct
All representations of a context free language are equivalent.
All representations of a recursive language are equivalent
Finite Automata are less powerful than Pushdown Automata.
FA is also called
Select correct option:
TG
GTG
NFA
DFA Correct
If an FA has N state then it must accept the word of length
Select correct option:
N-1 ok
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
Vukwl- Virtual Education Solution
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 ok
None of the given options
The reverse of the string sbfsbb over { sb, f, b }
Select correct option:
bbsfbs
bsbfsb
sbbfsb
bsfbsb
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
The product of two regular languages is __________.
Select correct option:
regular
infinite
non-regular
closure of a regular language
According to Myhill Nerode theorem, if L generates finite no. of classes then L is.......
Select correct option:
Finite
Infinite
Regular
Non regular
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
In pref(Q in R) Q is …… to (than) R
Select correct option:
Equal
Not equal
Greater
Smaller
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
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
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
If r1 and r2 are regular expressions then which of the following is not regular expressionr1 + r2
r1 r2
r1*
r1 – r2
Kleene star closure can be defined
Over any set of string
Over specific type of string
Which of following string(s) belongs to the language of the regular expression (aa*b)*?baabab
abbbaa
aaaaaa
aabaab
According to theory of automata there are _________ types of languages
Select correct option:One
Two Three
Four
If S = {aa, bb}, then S* will not containaabbaa
bbaabbbb
aaabbb aabbbb
Every non deterministic Finite Automata can be converted intoRegular Expression
Deterministic Finite Automata
Trasition Graph
All of the given options
The states in which there is no way to leave after entry are calledDavey John Lockers
Dead States
Waste Baskets
All of the given options
(a* + b*)* = (a + b)* this expression is _________
True False
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
FA is also calledTG
GTG
NFA
DFA
Kleene star closure can be defined
Over any set of string Over specific type of string
[(a + b)(a + b)]*, given RE cannot generate the string ________abbaabab
abbbaa
bbbbbb
abbbaaaaa
In an FA, when there is no path starting from initial state and ending in final state then that FAaccept null string
accept all strings
accept all non empty strings
does not accept any string
While finding RE corresponding to TG, we connect the new start state to the old start state by the transition labeled bya
b
null string None of the given options
According to theory of automata there are _________ types of languagesOne
Two
Three
Four
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
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
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
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 ok
may be good
always impossible
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 ok
Nm
mN
The strings or words which do not belong to a language is called…………. of that language
Select correct option:
Intersection
Union
Complement ok
Quotient
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
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 ok
may be good
always impossible
For language L defined over {a, b},then L partitions {a, b}* into …… classes
Select correct option:
Infinite ok
Finite
Distinct
Non distinct
Vukwl- Virtual Education Solution
If a regular expression contains * then it _______ define an ________ language.
Select correct option:
always, finite
may, infinite
always, infinite ok
None of the given options
Let FA3 be an FA corresponding to FA1FA2, then the initial state of FA3 must correspond to the initial state of
Select correct option:
FA1 only
FA2 only
FA1 or FA2
FA1 and FA2
In concatenation we accept the initial state of FA2 automatically after the final state of FA1 because of:
Select correct option:
We need just one initial state
We need exactly one final state
Some part of a string may be accepted by FA2
The strings of FA2 are accepted first before the strings of FA1
Even even
odd
Palindromes
Integers
Which of the following will be the final state of FA3 obtained from the union of FA1 and FA2?
Select correct option:
Final state of FA1
Final state of FA2
Final states of FA1 or FA2
Final states of FA1 or FA2 or both
Let FA1 accepts many strings and FA2 accepts none then FA1+FA2 will be equal to:
Select correct option:
FA1
FA2
FA2-FA1
(FA2)*
Let FA1 accepts many strings and FA2 accepts none then FA1+FA2 will be equal to:
Select correct option:
FA1
FA2
FA2-FA1
(FA2)*
The language {a ab aba bab} is _____ .
Select correct option:
Irregular
Regular
Recursive
None of the given options
Decomposing a string into its valid units is referred as:
Select correct option:
Decomposing
Splitting
Tokenizing
Dividing
The minimum length of the strings(except null string) of a language that starts and ends in different letters will be:
Select correct option:
1
2
3
4
Let FA3 be an FA corresponding to FA1+FA2, then the initial state of FA3
Must correspond to the initial state of
Select correct option:
FA1 only
FA2 only
FA1 or FA2
FA1 and FA2
If FA1 corresponds to (a+b)* then FA1 must accept ___________ string/strings. Select correct option: No Odd
length
Even length
Every
The minimum length of the strings(except null string) of a language that starts and ends in the same letters will be:
Select correct option:
1
2
3
4
A regular language can be:
Select correct option:
irregular
infinite
non-deterministic
None of the given options
Decomposing a string into its valid units is referred as:
Select correct option:
Decomposing
Splitting
Tokenizing
Dividing
We cannot construct an NFA for the language of ______ defined over alphabet set {a,b}.
Select correct option:
Even
even odd
Palindromes
Integers
In _______ there must be transition for all the lettersof a string.
Select correct option:
NFA
GTG
TG
FABC100403151 : Sidra Sahar Quiz Start Time: 06:43 PM Time Left 87 sec(s) Question # 7 of 10 ( Start time: 06:49:08 PM ) Total Marks: 1 For every three regular expressions R, S, and T, the languages denoted by R(S U T) and (RS) U (RT) are the ______ .
Select correct option:
Same Different
There ______ a language for which only FA can be built but not the RE.
Select correct option:
is cannot
be may
be may
not be
A regular language can be:
Select correct option:
irregular
infinite
non-deterministic
None of the given options
If FA1 corresponds to (a+b)* then FA1 must accept ___________ string/strings.
Select correct option:
No Odd
length
Even length
EveryConsider we have languages L7 and L6. Which of the following represents their concatenation? Select correct option:
L7+L6
L7/L6
L6L7
L7L6
Closure of an FA is the same as ___________ of an FA with itself except that the initial state of the required FA is a final state as well.
Select correct
The minimum length of the strings(except null string) of a language that starts and ends in different letters will be:
Select correct option:
1
2
3
4
In _______ there must be transition for all the lettersof a string.
Select correct option:
NFA
GTG
TG
FAFA and _______ are same except that _______ has unique symbol for each transition.
Select correct option:
FA,TG
NFA, TG
NFA, FA
GTG,NFA
If we have a finite language and the number of states in the FA is n then the maximum number of letters in the each word of the language that will be ac
1
n-1
n+1
n
Consider we have languages L7 and L6. Which of the following represents their concatenation? Select correct option:
L7+L6
L7/L6
L6L7
L7L6
Let FA3 be an FA corresponding to FA1FA2, then the final state of FA3 must correspond to the final state of
Select correct option:
FA1 only
FA2 only
FA1 or FA2
FA1 and FA2
The minimum length of the strings(except null string) of a language that starts and ends in the same letters will be:
Select correct option:
1
2
3
4
In pref(Q in R) Q is …… to (than) R
Select correct option:
Equal
Not equal
Greater ok
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 ok
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 ok
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
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
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
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
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
specified
finite -= Answer
odd
Vukwl- Virtual Education Solution
Which of the following is NOT a regular language?
Select correct option:
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
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
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:
Select correct option:
Nm +Nm+1+ N m+2 +… + N2m-1
mN +mN+1+ mN+2 +… +m2N-1 -= Answer
Nm
mN
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:
Select correct option:
3
4 -= Answer
5
6
4 -= Answer
5
6
In pref(Q in R) Q is …… to (than) R
Select correct option:
Select correct option:
Equal
Not equal -= Answer
Greater
Smaller
Not equal -= Answer
Greater
Smaller
If an effectively solvable problem has answer in yes or no, then this solution is called_______.
Select correct option:
Select correct option:
Infinite problem
decision procedure -= Answer
Finite solution
None of the given option
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
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
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
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
specified
finite -= Answer
odd
Vukwl- Virtual Education Solution
Which of the following is NOT a regular language?
Select correct option:
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
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
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:
Select correct option:
Nm +Nm+1+ N m+2 +… + N2m-1
mN +mN+1+ mN+2 +… +m2N-1 -= Answer
Nm
mN
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:
Select correct option:
3
4 -= Answer
5
6
4 -= Answer
5
6
In pref(Q in R) Q is …… to (than) R
Select correct option:
Select correct option:
Equal
Not equal -= Answer
Greater
Smaller
Not equal -= Answer
Greater
Smaller
If an effectively solvable problem has answer in yes or no, then this solution is called_______.
Select correct option:
Select correct option:
Infinite problem
decision procedure -= Answer
Finite solution
None of the given option
decision procedure -= Answer
Finite solution
None of the given option
To obtain an RE corresponding to the given TG , TG is converted into
Select correct option:
FA Correct
GTG
NFA
None of the given option
Let FA3 be an FA corresponding to FA1+FA2, then the final state of FA3 must correspond to the final state of
Select correct option:
FA1 only
FA2 only
FA1 or FA2 only Correct
FA1 or FA2 or both
While finding RE corresponding to TG, If TG has more than one start state then
Select correct option:
Introduce the new start state Correct
Replace the old start state with final state
Replace the old final state with new start state
Which of the following statement is true about GTG?
Select correct option:
Transitions are based on input letter Correct
Transitions are based on specified substring
Transitions are based on regular expression
None of the given options
Regular languages are closed under the following operations.
Select correct option:
Union only
Concatenation, Closure only
Union, Concatenation and Closure
Regular languages are not closed under any operation. Correct
Every non deterministic Finite Automata can be converted into
Select correct option:
Regular Expression
Deterministic Finite Automata
Trasition Graph
All of the given options Correct
Let FA3 be an FA corresponding to FA1+FA2, then the initial state of FA3 must correspond to the initial state of
Select correct option:FA1 only
FA2 only
FA1 or FA2 CorrectFA1* and FA2*
Which of the following statement is true about GTG?
Select correct option:
Transitions are based on input letter CorrectTransitions are based on specified substring
Transitions are based on regular expression
None of the given options
A language accepted by an FA is also accepted by
Select correct option:TG only
GTG only
RE only
All of the given Correct
While finding RE corresponding to TG, If TG has more than one start state then
Select correct option:
Introduce the new start state CorrectEliminate the old start state
Replace the old start state with final state
Replace the old final state with new start state
To obtain an RE corresponding to the given TG , TG is converted into
Select correct option:FA
GTG CorrectNFA
None of the given option
Which of the following statement is NOT true about TG?
Select correct option:
There exists exactly one path for certain string
There may exist more than one paths for certain string
There may exist no path for certain string
There may be no final state Correct
Every FA can be considered to be a
Select correct option:
TG CorrectRE
GTG
None of the given options
While finding RE corresponding to TG, we connect the new start state to the old start state by the transition labeled by
Select correct option:a
b
null string CorrectNone of the given options