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
While finding RE corresponding to TG, If TG has more than one start state then
Select correct option:Introduce the new start stateEliminate the old start state
Replace the old start state with final state
Replace the old final state with new start state
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 stringNone of the given options
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……
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
De-Morgan's law for sets is expressed by,
[IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image002.gif[/IMG]
[IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image002.gif[/IMG]
[IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image005.gif[/IMG]
[IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image007.gif[/IMG]
If L1 and L2 are regular languages, then these can be expressed by the corresponding FAs.
True
False
If an effectively solvable problem has answered in yes or no, then thissolution is called ---------
Decision procedure
Decision method
Decision problem
Decision making
ACCEPT
REJECT
STATR
READ
For language L defined over {a, b}, then L partitions {a, b}* into …… classes
Infinite
Finite
Distinct
Non-distinct
The production of the form: nonterminal --> one nonterminal is called the __________
Unit production
NULL production
Terminal production
Non Terminal production
CS402 Question # 2 of 10 (07:08:53 PM )
The production of the form: Nonterminal-> ^ is said to be ______ production
NULL
UNIT
Chomsky form production
None of the given options
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
While finding RE corresponding to TG, If TG has more than one start state then
Select correct option:Introduce the new start stateEliminate the old start state
Replace the old start state with final state
Replace the old final state with new start state
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 stringNone of the given options
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……
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
De-Morgan's law for sets is expressed by,
[IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image002.gif[/IMG]
[IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image002.gif[/IMG]
[IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image005.gif[/IMG]
[IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image007.gif[/IMG]
If L1 and L2 are regular languages, then these can be expressed by the corresponding FAs.
True
False
If an effectively solvable problem has answered in yes or no, then thissolution is called ---------
Decision procedure
Decision method
Decision problem
Decision making
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
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 FreeLanguage (CFL).
FA TG CFG TGT
Σ = {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)*
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
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
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 FreeLanguage (CFL).
FA TG CFG TGT
Σ = {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)*
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
The CFG is not said to be ambiguous if there exists atleast one word of itslanguage 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
A production is called null able production if it is of the form N → Λ
TRUE FALSE
The productions of the form nonterminal → one nonterminal, is called _________
Null production
Unit production
Null able production
None of given
CNF is stands for
Context Normal Form
Complete Normal Form
Chomsky Normal Form
Compared Null Form
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
A production is called null able production if it is of the form N → Λ
TRUE FALSE
The productions of the form nonterminal → one nonterminal, is called _________
Null production
Unit production
Null able production
None of given
CNF is stands for
Context Normal Form
Complete Normal Form
Chomsky Normal Form
Compared Null Form
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 regularlanguage.
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 Li.e. (Lc)c = Lc
True
False
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 regularlanguage.
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 Li.e. (Lc)c = Lc
True
False
If L is a regular language then, --------- is also a regular language.
Lm
Ls
Lx
Lc
Closure of an FA, is same as ___________ of an FA with itself, except
that the initial state of the required FA is a final state as well.
Select correct option:
Union
Sum
Concatenation (answer)
Intersection
If we have a fi the language that will be accepted by the given FA will be------------------------- 8) If R is a regular language and L is some language, and L U R is a regular language, then L must be a regular language.
Choices:
True
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 UL2 is not a regular.
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)*
17) 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 aNon 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 [IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image009.gif[/IMG]for n=1,2,3, … are the words in L. called.
Complement of L
Pumping Lemma
Kleene’s theorem
None in given
Lm
Ls
Lx
Lc
Closure of an FA, is same as ___________ of an FA with itself, except
that the initial state of the required FA is a final state as well.
Select correct option:
Union
Sum
Concatenation (answer)
Intersection
If we have a fi the language that will be accepted by the given FA will be------------------------- 8) If R is a regular language and L is some language, and L U R is a regular language, then L must be a regular language.
Choices:
True
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 UL2 is not a regular.
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)*
17) 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 aNon 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 [IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image009.gif[/IMG]for n=1,2,3, … are the words in L. called.
Complement of L
Pumping Lemma
Kleene’s theorem
None in given
Languages are proved to be regular or non regular using pumping lemma.
True
False
------------------- is obviously infinite language.
EQUAL-EQUAL
EVEN-EVEN
PALINDROME
FACTORIAL
If, two strings x and y, defined over Σ, are run over an FA accepting thelanguage 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 byPref(Q in R).
True False
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
___________ states are called the halt states.
ACCEPT and REJECT
ACCEPT and READ
ACCEPT AND START
ACCEPT AND WRITE
The part of an FA, where the input string is placed before it is run, is called _______
State
Transition
Input Tape
Output Tape
Which of the following regular expression represents same language? a. (a+ab)* b. (ba+a)* c. a*(aa*b)* d. (a*b*)*
Select correct option:
a and b
a and c
c and d
(a* + b*)* = (a + b)* this expression is __________
Select correct option:True
False
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
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 onlyFA1 or FA2FA1 and FA2
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 stringThere may be no final state
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.
What do automata mean?
Select correct option:
Something done manuallySomething done automatically
A language accepted by an FA is also accepted by
Select correct option:
TG only
GTG only
RE onlyAll of the given
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)*
Consider the Following CFG: (NOTE: ^ means NULL) S->Xa X->aX|bX|^ above given CFG can be represented by RE _________
Select correct option:
a*b*
a*b*a
(a+b)*a
a(a+b)*a
Identify FALSE statement:
Every Regular Expression be expressed by CFG and every CFG can be expressed by a Regular Expression
Every regular expression can be expressed as CFG but every CFG cannot be expressed as a regular expression.
For a PDA, there exists a CFG, that represents the same language as represented by PDA.
None of the given options
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
Null production is a
Word
String
Terminal
All of the given options
In nondeterministic PDA a string is supposed to be accepted, if there exists at least one path traced by the string, leading to ______ state.
ACCEPT
REJECT
START
READ
The CFG which generates the regular language is called
Regular expression
Finite Automata
Regular grammar
None of the given options
PDA stands for ________
Push and Drop Automaton
Pop and Drop Automaton
Push Down Automaton
None of given options
If a CFG has a null production, then it is possible to construct another CFG accepting the same language without null production
TRUE
FALSE
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
Halt states are
Start and Accept
Accept and Reject
Start and Reject
Read and Reject
The production of the form: Nonterminal-> ^ is said to be ______ production
NULL
UNIT
Chomsky form production
None of the given options
The production of the form: nonterminal --> one nonterminal is called the __________
Unit production
NULL production
Terminal production
Non Terminal production
The production of the form: Nonterminal-> ^ is said to be ______ production
NULL
UNIT
Chomsky form production
None of the given options
If a CFG has a null production, then it is ______
Posiible to construct another CFG without null production
accepting the same language with the exception of the
word ^
Not possible to construct another CFG without null production accepting the same
language with the exception of
the word ^
Called NULL CFG
Called Chmosky Normal Form (CNF)
Quiz : 07:08 88
A _________ is the one for which every input string has a unique path through the
machine.
deterministic PDA
nondeterministic PDA
PUSHDOWN store
Input Tape
In the null production N --> ^ , N is a
Terminal
Non terminal
Word
None of the given options
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
In polish notation, (o-o-o) is the abbreviation of………?
Operand - Operator – Operand
Operand - Operand- Operator
Operator -Operand – Operand
Operand -Operand – Operand
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
The input string is placed, before it runs, in
Stack
Memory
Tape
Ram
Which of the following states is not part of PDA
START
ACCEPT
WRTITE
REJECT
The production S --> SS | a | b | ^ can be expressed by RE
(a+b)+
(a+b)
(a+b)*
(ab)*
If a CFG has a null production, then it is ______
Posiible to construct another CFG without null production accepting the same
language with the exception of the
word ^
Not possible to construct another CFG without null production accepting the same
language with the exception of
the word ^
Called NULL CFG
Called Chmosky Normal Form (CNF)
The production of the form: nonterminal --> one nonterminal is called the __________
Unit production
NULL production
Terminal production
Non Terminal production
A _________ is the one for which every input string has a unique path through the
machine.
deterministic PDA
nondeterministic PDA
PUSHDOWN store
Input Tape
The locations into which we put the input letters on "Input Tap" are called __________
words
alphabets
cells
elements
"CFG" stands for _________
Context Free Graph
Context Free Grammer
Context Finite Graph
Context Finite Grammer
In a CFG the nonterminal that occurs first from the left in the working string, is said to be
________
Least Significant nonterminal
Most Significant nonterminal
Left most nonterminal
Left most derivate
The unit production is
Terminal --> Terminal
Terminal --> Non Terminal
Non terminal --> Terminal
Non terminal --> Non Terminal
A _____ operator adds a new letter at the top of STACK
PUSH
POP
READ
APPEND
PDA stands for ________
Push and Drop Automaton
Pop and Drop Automaton
Push Down Automaton
None of given options
Decomposing a string into its valid units is referred as:
Considering FA1 and FA2 having 2 states each. Now FA1+FA2 can have maximum ______________ number of states.
2
3
more than 3.
none of them
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
A string will be accepted by an NFA if there exist _______one successful path.
If R is a regular language and L is some language, and L U R is a _______, then L must be a ________.Regular language
True
False
------------------- is obviously infinite language.
EQUAL-EQUAL
EVEN-EVEN
PALINDROME
FACTORIAL
If, two strings x and y, defined over Σ, are run over an FA accepting thelanguage 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 byPref(Q in R).
True False
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
___________ states are called the halt states.
ACCEPT and REJECT
ACCEPT and READ
ACCEPT AND START
ACCEPT AND WRITE
The part of an FA, where the input string is placed before it is run, is called _______
State
Transition
Input Tape
Output Tape
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
(a* + b*)* = (a + b)* this expression is __________
Select correct option:True
False
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
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 onlyFA1 or FA2FA1 and FA2
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 stringThere may be no final state
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.
What do automata mean?
Select correct option:
Something done manuallySomething done automatically
A language accepted by an FA is also accepted by
Select correct option:
TG only
GTG only
RE onlyAll of the given
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)*
Consider the Following CFG: (NOTE: ^ means NULL) S->Xa X->aX|bX|^ above given CFG can be represented by RE _________
Select correct option:
a*b*
a*b*a
(a+b)*a
a(a+b)*a
Identify FALSE statement:
Every Regular Expression be expressed by CFG and every CFG can be expressed by a Regular Expression
Every regular expression can be expressed as CFG but every CFG cannot be expressed as a regular expression.
For a PDA, there exists a CFG, that represents the same language as represented by PDA.
None of the given options
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
Null production is a
Word
String
Terminal
All of the given options
In nondeterministic PDA a string is supposed to be accepted, if there exists at least one path traced by the string, leading to ______ state.
ACCEPT
REJECT
START
READ
The CFG which generates the regular language is called
Regular expression
Finite Automata
Regular grammar
None of the given options
PDA stands for ________
Push and Drop Automaton
Pop and Drop Automaton
Push Down Automaton
None of given options
If a CFG has a null production, then it is possible to construct another CFG accepting the same language without null production
TRUE
FALSE
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
Halt states are
Start and Accept
Accept and Reject
Start and Reject
Read and Reject
The production of the form: Nonterminal-> ^ is said to be ______ production
NULL
UNIT
Chomsky form production
None of the given options
The production of the form: nonterminal --> one nonterminal is called the __________
Unit production
NULL production
Terminal production
Non Terminal production
The production of the form: Nonterminal-> ^ is said to be ______ production
NULL
UNIT
Chomsky form production
None of the given options
If a CFG has a null production, then it is ______
Posiible to construct another CFG without null production
accepting the same language with the exception of the
word ^
Not possible to construct another CFG without null production accepting the same
language with the exception of
the word ^
Called NULL CFG
Called Chmosky Normal Form (CNF)
Quiz : 07:08 88
A _________ is the one for which every input string has a unique path through the
machine.
deterministic PDA
nondeterministic PDA
PUSHDOWN store
Input Tape
In the null production N --> ^ , N is a
Terminal
Non terminal
Word
None of the given options
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
In polish notation, (o-o-o) is the abbreviation of………?
Operand - Operator – Operand
Operand - Operand- Operator
Operator -Operand – Operand
Operand -Operand – Operand
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
The input string is placed, before it runs, in
Stack
Memory
Tape
Ram
Which of the following states is not part of PDA
START
ACCEPT
WRTITE
REJECT
The production S --> SS | a | b | ^ can be expressed by RE
(a+b)+
(a+b)
(a+b)*
(ab)*
If a CFG has a null production, then it is ______
Posiible to construct another CFG without null production accepting the same
language with the exception of the
word ^
Not possible to construct another CFG without null production accepting the same
language with the exception of
the word ^
Called NULL CFG
Called Chmosky Normal Form (CNF)
The production of the form: nonterminal --> one nonterminal is called the __________
Unit production
NULL production
Terminal production
Non Terminal production
A _________ is the one for which every input string has a unique path through the
machine.
deterministic PDA
nondeterministic PDA
PUSHDOWN store
Input Tape
The locations into which we put the input letters on "Input Tap" are called __________
words
alphabets
cells
elements
"CFG" stands for _________
Context Free Graph
Context Free Grammer
Context Finite Graph
Context Finite Grammer
In a CFG the nonterminal that occurs first from the left in the working string, is said to be
________
Least Significant nonterminal
Most Significant nonterminal
Left most nonterminal
Left most derivate
The unit production is
Terminal --> Terminal
Terminal --> Non Terminal
Non terminal --> Terminal
Non terminal --> Non Terminal
A _____ operator adds a new letter at the top of STACK
PUSH
POP
READ
APPEND
PDA stands for ________
Push and Drop Automaton
Pop and Drop Automaton
Push Down Automaton
None of given options
Closure of an FA is same as concatenation of an FA with itself?
True
False
In Closure of an FA the initial state of a required FA is
Initial state of another FA
Final State of another FA
Final state as well of the same FA
None of the Given
NFA is a TG as well?
True
False
Considering FA1 and FA2 having 2 states each. Now FA1+FA2 can have maximum number of states.
2
3
It will be more than 3.
None of them
Closure of an FA, is same as of an FA with itself, except
that the initial state of the required FA is a final state as well.
Union
Sum
Concatenation (answer)
Intersection
If R is a regular language and L is some language, and L U R is a regular language, then L must be a regular language.
True
False
If R is a regular language and L is some language, and L U R is a RE then L must be a
Concatenation
Regular Language
There a unique path for each string in NFA?
Must be
May be
Should be
May not be
If a Language is accepted by an FA then there exists a TG accepting the language?
True
False
It is clear by the definition of NFA that a string is supposed to be accepted if there exist at least successful path
Two
One
More than one
More than two
Can NFA and FA be equivalent?
Yes
No
NFA helps to eliminate at certain state of an FA
Loop
FA
NFA
String
It is possible to convert an FA into NFA?
True
False
nite language and the number of states in the FA is n then the maximum number of letters in the each word of1) The minimum length of the strings(except null string) of a language that starts and ends in the same letters will beTrue
False
In Closure of an FA the initial state of a required FA is
Initial state of another FA
Final State of another FA
Final state as well of the same FA
None of the Given
NFA is a TG as well?
True
False
Considering FA1 and FA2 having 2 states each. Now FA1+FA2 can have maximum number of states.
2
3
It will be more than 3.
None of them
Closure of an FA, is same as of an FA with itself, except
that the initial state of the required FA is a final state as well.
Union
Sum
Concatenation (answer)
Intersection
If R is a regular language and L is some language, and L U R is a regular language, then L must be a regular language.
True
False
If R is a regular language and L is some language, and L U R is a RE then L must be a
Concatenation
Regular Language
There a unique path for each string in NFA?
Must be
May be
Should be
May not be
If a Language is accepted by an FA then there exists a TG accepting the language?
True
False
It is clear by the definition of NFA that a string is supposed to be accepted if there exist at least successful path
Two
One
More than one
More than two
Can NFA and FA be equivalent?
Yes
No
NFA helps to eliminate at certain state of an FA
Loop
FA
NFA
String
It is possible to convert an FA into NFA?
True
False
NFA helps to eliminate loop at certain state of an FA in this process loop is converted into
String
Circuit
Can be considered as intermediate structure between FA and TG
GTG
NFA
Artificial Intelligence is important example of
FA
GTG
TG
NFA
Enjoy J
String
Circuit
Can be considered as intermediate structure between FA and TG
GTG
NFA
Artificial Intelligence is important example of
FA
GTG
TG
NFA
Enjoy J
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
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
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
FA
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
Every
Consider 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
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
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
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
FA
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
Every
Consider 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
Decomposing a string into its valid units is referred as:
Considering FA1 and FA2 having 2 states each. Now FA1+FA2 can have maximum ______________ number of states.
2
3
more than 3.
none of them
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
A string will be accepted by an NFA if there exist _______one successful path.
If R is a regular language and L is some language, and L U R is a _______, then L must be a ________.Regular language
CS402 Theory of Automata- Imcqs solved CS402 Theory of Automata- Iquiz mega file CS402 Theory of Automata- Imidterm solved papers 2017 CS402 Theory of Automata- Isolved mcqs mega file CS402 Theory of Automata- Imidterm solved papers 2016 CS402 Theory of Automata- I midterm papers CS402 Theory of Automata- Ifinal term solved mcqs mega file CS402 Theory of Automata- I handouts CS402 Theory of Automata- Ilectures CS402 Theory of Automata- I assignment CS402 Theory of Automata- Ihandouts CS402 Theory of Automata- I assignment solution 2018 CS402 Theory of Automata- Ippt slides CS402 Theory of Automata- Iassignment no 2 solution 2018 CS402 Theory of Automata- Imidterm solved papers by moaaz CS402 Theory of Automata- Ifinal term solved mcqs by moaaz