CS402- MCQ,s
For a given input, it provides the compliment of Boolean AND
output.
NAND
box (NOT AND)
DELAY box
OR box
AND box
It
delays the transmission of signal along the wire by one step (clock pulse).
NAND box (NOT AND)
DELAY
box
OR box
AND box
For the
given input, it provides the Boolean OR output
NAND box (NOT AND)
DELAY box
OR
box
AND box
For the
given input, AND box provides the Boolean AND output.
True False
The
current in the wire is indicated by 1 and 0 indicates the absence of the current.
True False
Any
language that can not be expressed by a RE is said to be regular language.
True False
If L1
and L2 are regular languages is/are also regular language(s).
L1 + L2
L1L2
L1*
All of above
Let L be
a language defined over an alphabet Σ, then the language of strings, defined
over Σ, not belonging to L, is called Complement of the language L, denoted by Lc or L’.
True False
To
describe the complement of a language, it is very important to describe the
----------- of that language over which the language is defined.
Alphabet
Regular
Expression
String
Word
For a
certain language L, the complement of Lc is the given language L i.e.
(Lc)c = Lc
True False
If L is a regular language then, --------- is also a regular
language.
Lm Ls Lx Lc
Converting each of the final states of F to non-final states
and old non-final states of F to final states, FA thus obtained will reject
every string belonging to L and will accept every string, defined over Σ, not
belonging to L. is called
Transition Graph of L
Regular expression of L
Complement
of L
Finite Automata of L
If L1
and L2 are two regular languages, then L1 U L2 is
not a regular.
True False
De-Morgan's
law for sets is expressed by,
CORRECT
If L1 and L2 are regular languages, then these can be
expressed by the corresponding FAs.
True False
L=
language of words containing even number of a’s. Regular Expression is
(a+b)*aa(a+b)*
(b+ab*a)*
a+bb*aab*a
(a+b)*ab(a+b)*
The regular expression defining the language L1 U L2 can be obtained,
converting and reducing the previous ------------- into a ------------ as after
eliminating states.
GTG, TG
FA,
GTG
FA, TG
TG, RE
The
language that can be expressed by any regular expression is called a Non
regular language.
True False
The languages -------------- are the examples of non regular
languages.
PALINDROME and PRIME
PALINDROME and
EVEN-EVEN
EVEN-EVEN and PRIME
FACTORIAL and SQURE
Let L be
any infinite regular language, defined over an alphabet Σ then there exist three strings
x, y and z belonging to Σ*
such that all the strings of the form 
for n=1,2,3, … are the words in L. called.
for n=1,2,3, … are the words in L. called.
Complement
of L
Pumping Lemma
Kleene’s
theorem
None in
given
(21) Languages
are proved to be regular or non regular using pumping lemma.
True False
(22) -------------------
is obviously infinite language.
EQUAL-EQUAL
EVEN-EVEN
PALINDROME
FACTORIAL
(23) If, two strings x and y, defined
over Σ, are
run over an FA accepting the language L, then x and y are said to belong to the
same class if they end in the same state, no matter that state is final or not.
True False
Myhill Nerode theorem
is consisting of the followings,
L
partitions Σ* into
distinct classes.
If L is
regular then, L generates finite number of classes.
If L
generates finite number of classes then L is regular.
All of above
The
language Q is said to be quotient of two regular languages P and R, denoted by--- if PQ=R.
R=Q/P Q=R/P Q=P/R P=R/Q
If two
languages R and Q are given, then the prefixes of Q in R denoted by Pref(Q
in R).
True False
(27) Let Q = {aa, abaaabb, bbaaaaa,
bbbbbbbbbb} and R = {b, bbbb, bbbaaa, bbbaaaaa} Pref (Q in R) is equal to,
{b,bbba,bbbaaa}
{b,bba,bbaaa}
{ab,bba,bbbaa}
{b,bba,bbba}
If R is
regular language and Q is any language (regular/ non regular), then Pref (Q in R)
is ---------.
Non-regular
Equal
Regular
Infinite
"CFG" stands for _________
Context Free Graph
Context
Free Grammar
Context Finite Graph
Context Finite Grammar
(29) ___________
states are called the halt states.
ACCEPT
and REJECT
ACCEPT and READ
ACCEPT AND START
ACCEPT AND WRITE
(30) The part of an
FA, where the input string is placed before it is run, is called _______
State
Transition
Input
Tape
Output Tape
In new format of an FA (discussed in lecture 37), This state
is like dead-end non final state
ACCEPT
REJECT
STATR
READ
For language L defined over {a, b}, then L partitions {a, b}*
into …… classes
Infinite
Finite
Distinct
Non-distinct
The major problem in the earliest computers was
To store the contents in the registers
To
display mathematical formulae
To load the contents from the registers
To calculate the mathematical formula
Between the two consecutive joints on a path
One character can be pushed and one character can be popped
Any
no. of characters can be pushed and one character can be popped
One character can be pushed and any no. of characters can be
popped
Any no. of characters can be pushed and any no. of characters
can be popped
(35) In pumping lemma
theorem (x y^n z) the range of n is
n=1,
2, 3, 4……….
n=0, 1, 2, 3, 4……….
n=…….-3,-2,-1, 0, 1, 2, 3, 4……
n=…….-3,-2,-1, 1, 2, 3, 4……
(36) The PDA is
called non-deterministic PDA when there are more than one out going edges
from……… state
START or READ
POP or REJECT
READ
or POP
PUSH or POP
Identify the TRUE statement:
A PDA is non-deterministic, if there are more than one READ
states in PDA
A PDA is never non-deterministic
Like
TG, A PDA can also be non-deterministic
A PDA is non-deterministic, if there are more than one REJECT
states in PDA
There is
a problem in deciding whether a state of FA should be marked or not when the
language Q is infinite.
True False
If an
effectively solvable problem has answered in yes or no, then this solution is
called ---------
Decision procedure
Decision
method
Decision
problem
Decision
making
The
following problem(s) ------------- is/are called decidable problem(s).
The two
regular expressions define the same language
The two
FAs are equivalent
Both a and b
None of
given
To
examine whether a certain FA accepts any words, it is required to seek the
paths from ------- state.
Final to
initial
Final to
final
Initial to final
Initial
to initial
The high
level language is converted into assembly language codes by a program called
compiler.
TRUE FALSE
Grammatical
rules which involve the meaning of words are called ---------------
Semantics
Syntactic
Both a and b
None of given
Grammatical
rules which do not involve the meaning of words are called ---------------
Semantics
Syntactic
Both a and b
None of given
The
symbols that can’t be replaced by anything are called -----------------
Productions
Terminals
Non-terminals
All of
above
The
symbols that must be replaced by other things are called __________
Productions
Terminals
Non-terminals
None of
given
(47) The grammatical rules are often
called_____________
Productions
Terminals
Non-terminals
None of
given
The
terminals are designated by ________ letters, while the non-terminals are
designated by ________ letters.
Capital,
bold
Small, capital
Capital,
small
Small,
bold
The
language generated by __________ is called Context Free Language (CFL).
FA TG CFG TGT
(49) Σ = {a,b} Productions S→XaaX X→aX X→bX X→Λ
This grammar defines the language expressed by___________
(a+b)*aa(a+b)*
(a+b)*a(a+b)*a
(a+b)*aa(a+b)*aa
(a+b)*aba+b)*
(50) S
→ aXb|b XaX →
aX|bX|Λ The given CFG
generates the language in English __________
Beginning
and ending in different letters
Beginning and ending in same letter
Having even-even language
None of given
(51) The CFG is not said to be
ambiguous if there exists atleast one word of its language that can be
generated by the different production trees,
TRUE FALSE
The
language generated by that CFG is regular
if _________
No
terminal → semi
word
No
terminal → word
Both a and b
None of
given
The
production of the form no terminal → Λ is said to be null production.
TRUE FALSE
(54) A production is called null able
production if it is
of the form N → Λ
TRUE FALSE
(55) The productions of the form nonterminal → one nonterminal, is called
_________
Null
production
Unit production
Null able production
None of given
(56) CNF is stands for
Context Normal Form
Complete Normal Form
Chomsky Normal Form
Compared Null Form
Proof(Kleene’s Theorem Part II)
If a TG has more than
one start states, then
Introduce the new start state
Eliminate the old start state
Replace the old start state with final state
Replace the old final state with new start state
Question # 2
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
None of the given options
Select correct option:
a
b
null string
None of the given options
Question # 3 of 10 ( Start time: 05:49:03 PM ) Total Marks: 1
Which of the following regular expression represents same language? a. (a+ab)* b. (ba+a)* c. a*(aa*b)* d. (a*b*)*
Which of the following regular expression represents same language? a. (a+ab)* b. (ba+a)* c. a*(aa*b)* d. (a*b*)*
a+b)*a(a+b)*b(a+b)*+ (a+b)*b(a+b)*a(a+b)*.
{ x}*, { x}+, {a+b}*
Select correct option:
a and b
a and c
c and d
Question # 4 of 10 ( Start time: 05:50:32 PM ) Total Marks: 1
(a* + b*)* = (a + b)* this expression is __________
Select correct option:
True
False
(a* + b*)* = (a + b)* this expression is __________
Select correct option:
True
False
Question # 5 of 10 ( Start time:
05:51:30 PM ) Total Marks: 1
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
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
Question # 6 of 10 ( Start time: 05:53:01 PM ) Total Marks: 1
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
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
Question # 7 of 10 ( Start time: 05:54:06 PM ) Total Marks: 1
Kleene’s theorem states
Select correct option:
All representations of a regular language are equivalent.
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.
Kleene’s theorem states
Select correct option:
All representations of a regular language are equivalent.
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.
Question # 8 of 10 (Start time: 05:55:36 PM ) Total Marks: 1
What do automata mean?
Select correct option:
Something done manually
Something done automatically
What do automata mean?
Select correct option:
Something done manually
Something done automatically
Question # 9 of 10 ( Start time: 05:56:51 PM ) Total Marks: 1
A language accepted by an FA is also accepted by
Select correct option:
TG only
GTG only
RE only
All of the given
A language accepted by an FA is also accepted by
Select correct option:
TG only
GTG only
RE only
All of the given
Question # 10 of 10 ( Start time:
05:58:16 PM ) Total Marks: 1
If r1 = (aa + bb) and r2 = (a + b) then the language (aa + bb)(a + b) will be generated by
Select correct option:
(r1)(r2)
(r1 + r2)
(r2)(r1)
(r1)*
If r1 = (aa + bb) and r2 = (a + b) then the language (aa + bb)(a + b) will be generated by
Select correct option:
(r1)(r2)
(r1 + r2)
(r2)(r1)
(r1)*
|
Question
# 1 of 10 ( Start time:
|
Total Marks: 1
|
||||||||
Alphabet S = {a, bc, cc} has __3__ number of letters
|
|||||||||
 Select correct option: |
|||||||||
|
|
|||||||||
|
|||||||||
|
Question
# 2 of 10 ( Start time:
|
Total Marks: 1
|
|
If
S = { x }, then S* will be
|
|
{x,xx,xxx,xxxx,…}
{^ ,x,xx,xxx,xxxx,…}
|
Question
# 3 of 10 ( Start time:
|
Total Marks: 1
|
||||||||||
|
Length
of EVEN-EVEN language is _________
|
|||||||||||
|
Select
correct option:
|
|||||||||||
|
|
|||||||||||
|
|||||||||||
|
Question
# 4 of 10 ( Start time:
|
Total Marks: 1
|
|
If
r1 = (aa + bb) and r2 = (a + b) then the language (aa + bb)(a + b) will be
generated by
|
|
|
Question
# 5 of 10 ( Start time:
|
Total Marks: 1
|
|
If
S = {aa, bb}, then S* will not contain
|
|
Aabbaa
Bbaabbbb
Aaabbb
aabbaaaa
|
Question
# 6 of 10 ( Start time:
|
Total Marks: 1
|
|
Formal
is also known as _________
|
|
Syntactic language
Semantic language
Informal language
None of these
|
Question
# 7 of 10 ( Start time:
|
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
# 9 of 10 ( Start time:
|
Total Marks: 1
|
|
FA
of EVEN language shows null string when
|
|
Initial state is final as well
EVEN does not accept null
One state is declared null
None of the these
Question No: 1 (
Marks: 1 ) - Please choose one
If
r1 = (aa + bb) and r2 = ( a + b) then the language (aa + bb)(a + b) will be
generated by
► (r1)(r2)
*► (r1 + r2)
► (r2)(r1)
► (r1)*
Question
No: 2 ( Marks: 1 ) - Please choose one
“One
language can be expressed by more than one FA”. This statement is ______
* ► True
► False
► Some times
true & sometimes false
► None of these
Question No: 3 (
Marks: 1 ) - Please choose one
Who
did not invent the Turing machine?
► Alan Turing
*► A. M. Turing
► Turing
► None of these
Question No: 4 (
Marks: 1 )- Please choose one
Which
statement is true?
*► The tape of turing machine is
infinite.
► The tape of
turing machine is finite.
► The tape of
turing machine is infinite when the language is regular
► The tape of
turing machine is finite when the language is nonregular.
Question No: 5 (
Marks: 1 ) - Please choose one
A
regular language:
► Must be finite
► Must be infinite
► Can be finite
or infinite
► Must be finite
and cannot be infinite
Question No: 6 (
Marks: 1 ) - Please choose one
Every
regular expression can be expressed as CFG but every CFG cannot be expressed as
a regular expression. This statement is:
► Depends on the
language
► None of the
given options
*► True
► False
Question No: 7 (
Marks: 1 ) - Please choose one
Above given FA corresponds RE r. then FA corresponding to r*
will be
This statement is
*► True
► False
► Depends on language
► None of these
Question No: 8 (
Marks: 1 ) - Please choose one
Consider
the language L of strings, defined over Σ = {a,b}, ending in a
► There are finite many classes
generated by L, so L is regular
*►
There are infinite
many classes generated by L, so L is regular
► There are finite many classes
generated by L, so L is non-regular
► There are infinite many
classes generated by L, so L is non-regular
Question No: 9 (
Marks: 1 ) - Please choose one
Above given TG has _____________ RE.
►
(aa+aa+(ab+ab)(aa+ab)*(ab+ba))*
*►
(aa+bb+(ab+ba)(aa+bb)*(ab+ba))*
►
(aa+bb+(ab+ba)(aa+bb)(ab+ba))*
► None of these
Question No: 10 (
Marks: 1 ) - Please choose one
The
word ‘formal’ in formal languages means
*► The symbols used have well defined meaning
► They are
unnecessary, in reality
► Only the form
of the string of symbols is significant
► None of these
Question No: 11 (
Marks: 1 ) - Please choose one
Let
A = {0, 1}. The number of possible strings of length ‘n’ that can be formed by
the elements of the set A is
► n!
*► n2
► nm
► 2n
Question No: 12 (
Marks: 1 ) - Please choose one
Choose
the correct statement.
► A Mealy
machine generates no language as such
► A Moore
machine generates no language as such
*► A Mealy machine has no
terminal state
► All of these
Question No: 13 (
Marks: 1 ) - Please choose one
TM
is more powerful than FSM because
► The tape
movement is confined to one direction
*► It has no finite state
control
► It has the
capability to remember arbitrary long sequences of input symbols
► None of these
Question No: 14 (
Marks: 1 ) - Please choose one
If
L1 and L2 are expressed by regular expressions r1 and r2, respectively then the language expressed
by r1 + r2 will be _________
* ► Regular
► Ir-regular
► Can’t be
decided
► Another
Language which is not listed here
Question No: 15 (
Marks: 1 ) - Please choose one
Like
TG, a PDA can also be non-deterministic
► True
*► False
Question No: 16 (
Marks: 1 ) - Please choose one
The above machine is a/anTG ___________
► Finite
Automata
*► Turing machine
► FA
► TG
Question No: 17 (
Marks: 1 ) - Please choose one
The
language of all words (made up of a’s and b’s) with at least two a’s can not be
described by the regular expression.
► a(a+b)*a(a+b)*(a+b)*ab*
► (a+b)* ab* a(a+b)*
► b*ab* a(a+b)*
► none of these
Question No: 18 (
Marks: 1 ) - Please choose one
In
FA, if one enters in a specific state but there is no way to leave it, then
that specific state is called
*► Dead State
► Waste Basket
► Davey John
Locker
► All of these
Question No: 19 (
Marks: 1 ) - Please choose one
If
L is a regular language then, Lc is also a _____ language.
*► Regular
► Non-regular
► Regular but
finite
► None of the
given
Question No: 20 (
Marks: 1 ) - Please choose one
In
CFG, the symbols that can’t be replaced by anything are called___
► Terminal
► Non-Terminal
*► Production
► All of given
Question No: 21 (
Marks: 1 ) - Please choose one
Which
of the following is NOT a regular language?
► String of 0’s
whose length is a perfect squere
*► Set of all palindromes made up of 0’s and 1’s
► String of 0’s
whose length is a prime number
► All of the given options
Question No: 22 (
Marks: 1 ) - Please choose one
Choose
the incorrect (FALSE) statement.
► A Mealy
machine generates no language as such
► A Mealy
machine has no terminal state
*► For a given input string,
length of the output string generated by a Moore machine is not more than the
length of the output string generated by that of a Mealy machine
► All of these
Question No: 23 (
Marks: 1 ) - Please choose one
Pumping
lemma is generally used to prove that:
► A given
language is infinite
*► A given language is not
regular
► Whether two
given regular expressions of a regular language are equivalent or not
► None of these
Question No: 24 (
Marks: 1 ) - Please choose one
Which
of the following is a regular language?
► String of odd
number of zeroes
► Set of all
palindromes made up of 0’s and 1’s
*► String of
0’s whose length is a prime number
► All of these
Question No: 25 (
Marks: 1 ) - Please choose one
Choose
the incorrect statement:
► (a+b)*aa(a+b)*
generates Regular language.
► A language
consisting of all strings over ∑={a,b} having equal number of a’s and b’s is a regular language
► Every language
that can be expressed by FA can also be
expressed by RE
► None of these
Question No: 26 (
Marks: 1 ) - Please choose one
Left
hand side of a production in CFG consists of:
► One terminal
► More than one
terminal
► One
non-terminal
* ► Terminals and
non-terminals
No comments:
Post a Comment