Vu All Subjects Assignment Quiz GDB Handouts Available here
Aslam U Alaikum!
Dear Students
This is to inform you that a Combined Quiz No. 03 and Quiz No. 04 of CS402 will get open on Monday January 30, 2023 and will be closed on Tuesday January 31, 2023. Lecture No. 23 to 30 will be included in this quiz.
It is advised to attempt the quiz as soon as it is opened to avoid any LMS/internet issues on last day.
If you failed to attempt the quiz in given time then no re-take or off line quiz will be held as compensation/replacement.
For a non-regular language, there exists ___________ FA.
no
If a language generates finite number of distinct classes then it must be _____________.
regular
The language L defined over Σ, not belonging to L is cased __________ of the language L.
Complement
Which of the following refers to the set of strings of
strings of letters that when concatenated to the front of the some word in Q produces
some same word in R?
Pref(R in Q)
The string or words which do not belong to a language are
called __________of that language?
Complement
The strings or words which do not belong to a language is
called __________ of that language
Complement
Even-palindrome is a __________ language.
Non-regular
In a new format of an FA, this state is like dead-end non
final state
REJECT
In new format of an FA, This state is like dead-end non
final state
REJECT
What turing machine does not have?
word
The grammatical rules which involves meaning of words are
called
Semantic
Kleene star closure
can be defined
Over any set of
string
The string or words
which do not belong toa language is called __________ of that language
complement
Formal is also knowsn
as __________
syntatic language
PDA is only used to
represent a regular langugage.
FALSE
An FSM can be
considered as TM
Of finite tape
length, without rewinding capability and unidirectional tape movement
The regular
expression defining the language L1 L2 can be obtained, convereting and
reducing the previous __________ into a __________ as after eliminating states
FA,GTG
For a machine with N
number of states the total number of strings to be tested, defined over an
alphabet of m letter is __________
m^N+m^N+1+m^N+2+----------+m2N-1
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 }
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
In pref(Q in R), Q is _____ to to/ than R.
Not equal
Prime is a _ _ _ _ _ _
language.
Non regular
The language of all strings not beginning with partitions
“b" into distinct classes.
Two
A problem is said to be _________ if there exists an
algorithm that provides the solution in __________ number of steps.
effectively solvable, finite
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
An FA has same initial and _____ state, then it means that
it has no _______ state.
Select correct option:
final, initial
The product of two regular languages is __________.
regular
According to Myhill Nerode theorem, if L generates finite
no. of classes then L is.......
Select correct option:
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
May be final state or not
In pref(Q in R) Q is …… to (than) R
Not equal
For language L defined over {a, b},then L partitions {a, b}*
into …… classes
Distinct
Which of the following is not a true theorem?
Pseudo theorem
If a regular expression contains * then it _______ define an
________ language.
may, infinite
a^n b^n generates the ………… language
non regular
To examine whether a certain FA accepts any words, it is
required to seek the paths
_______ state.
from initial to final
If r1 and r2 are regular expressions then which of the
following is not regular expression
r1 – r2
Kleene star closure can be defined
Over any set of string
Which of following string(s) belongs to the language of the
regular expression (aa*b)*?
aabaab
According to theory of automata there are _________ types of
languages
Select correct option:
Two
If S = {aa, bb}, then S* will not contain
aaabbb
Every non deterministic Finite Automata can be converted
into
Regular Expression
Deterministic Finite Automata
Trasition Graph
All of
the given options
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
(a* + b*)* = (a + b)* this expression is _________
True
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 called
DFA
Kleene star closure can be defined
Over any set of string
[(a + b)(a + b)]*, given RE cannot generate the string
________
bbbbbb
In an FA, when there is no path starting from initial state
and ending in final state then
that FA
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 by
null string
According to theory of automata there are _________ types of
languages
Two
While finding RE corresponding to TG, If TG has more than
one final state then
Introduce the new final state
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
What is false about the term alphabet?
It can be an empty set.
Which of the following is used to delay the transmission of
signal along the wire by one step (clock pulse)?
Delay box
Thanks everone