Last updated
1. Let
R1 and
R2 be regular sets defined over alphabet
∑ then
R1∪R2 is regular
∑∩R2is not regular
R1∩R2 is not regular
Show me the answer
Answer: 1. R1∪R2 is regular
Explanation:
The union of two regular sets is also regular.
2. Consider the production of the grammar
S→AA
A→aa
A→bb
Describe the language specified by the production grammar
L={aaaa,aabb,bbaa,bbbb}
L={abab,abaa,aaab,baaa}
L={aaab,baba,bbaa,bbbb}
L={aaaa,ababa,bbaa,aaab}
Show me the answer
Answer: 1. L={aaaa,aabb,bbaa,bbbb}
Explanation:
The grammar generates strings of even length with a and b.
3. Give a production grammar that specifies the language
Show me the answer
4. Which of the following string can be obtained by the language
Show me the answer
Answer: 4. aaaabbbbbb
Explanation:
Show me the answer
Show me the answer
7. Give a production grammar for the language
Show me the answer
Show me the answer
Answer: 3. Type-3 grammar
Explanation:
The grammar is a regular (Type-3) grammar as it generates regular languages.
9. Which of the following statement is wrong?
A Turing machine cannot solve halting problem
Set of recursively enumerable languages is closed under union
A finite State Machine with 2 stacks
Context sensitive grammar can be recognized by a linearly bounded memory machine
Show me the answer
Answer: 3. A finite State Machine with 2 stacks
Explanation:
A finite state machine cannot have 2 stacks; it is a characteristic of a pushdown automaton.
10. Which of the following statement is wrong?
Recursive language are closed under union
Recursive language are closed under union
If a language and its complement are both regular, then the language must be recursive
A language is accepted by FA if and only if it is recursive
Show me the answer
Answer: 4. A language is accepted by FA if and only if it is recursive
Explanation:
A language accepted by a finite automaton (FA) is regular, not necessarily recursive.
11. Which of the following statement is wrong?
Every recursive language is recursively enumerable
A language is accepted by FA if and only if it is context free
Recursive languages are closed under intersection
A language is accepted by a FA if and only if it is right linear
Show me the answer
Answer: 2. A language is accepted by FA if and only if it is context free
Explanation:
A language accepted by a finite automaton (FA) is regular, not necessarily context-free.
12. Which of the following statement is true?
All language can be generated by CFG
Any regular language has an equivalent CFG
The class of CFG is not closed under union
Show me the answer
Answer: 3. Any regular language has an equivalent CFG
Explanation:
Every regular language can be represented by a context-free grammar (CFG).
13. Recursively enumerable languages are not closed under
Show me the answer
Answer: 1. Complementation
Explanation:
Recursively enumerable languages are not closed under complementation.
Show me the answer
Show me the answer
Show me the answer
Show me the answer
18. The regular expression has all strings in which any number of 0's is followed by any number of 1's followed by any number of 2's is:
Show me the answer
19. The regular expression have all strings of 0's and 1's with no two consecutive 0's, is
Show me the answer
20. The regular expression with all strings of 0's and 1's with at least two consecutive 0's is:
Show me the answer
Show me the answer
Answer: 4. Abababab
Explanation:
22. Which string can be generated by
Show me the answer
Answer: 1. Aabccd
Explanation:
23. The regular sets are closed under
Show me the answer
Answer: 4. All of the above
Explanation:
Regular sets are closed under union, Kleene's closure, and concatenation.
24. Which of the following statement(s) is (are) wrong?
The regular sets are closed under intersection
The class of regular sets is closed under substitution
The class of regular sets is closed under homomorphisms
Context sensitive Grammar (CGS) can be recognized by Finite State Machine
Show me the answer
Answer: 4. Context sensitive Grammar (CGS) can be recognized by Finite State Machine
Explanation:
Context-sensitive grammars cannot be recognized by finite state machines.
25. A Finite State Machine can be considered, having finite tape length without rewinding capability and unidirectional tape movement
Show me the answer
Answer: 1. Turing machine
Explanation:
A finite state machine with finite tape length and unidirectional tape movement behaves like a Turing machine.
26. Which of the following statement is wrong?
A finite state machine can be considered to be a Turing Machine of finite tape length without rewinding capability and unidirectional tape movement
Turing machine is more powerful than finite state machine because it has the capability to remember arbitrary long sequences of input symbol
Palindromes can't be recognized by any Finite State Machine (FSM) because an FSM can't remember arbitrarily large amount of information
Turing machine is more powerful than FMS because it has no final state
Show me the answer
Answer: 4. Turing machine is more powerful than FMS because it has no final state
Explanation:
Turing machines are more powerful due to their ability to read/write and move in both directions, not because they lack a final state.
Context-sensitive language
Recursively enumerable language
Show me the answer
Answer: 1. Regular language
Explanation:
The reverse of a regular language is also regular.
Recursively enumerable language
Context-sensitive language
Show me the answer
Answer: 4. Context free language
Explanation:
The grammar is context-free as it generates a context-free language.
29. Any given transition graph has an equivalent
DFSM (Deterministic Finite State Machine)
Show me the answer
Answer: 4. All of them
Explanation:
A transition graph can be converted into a regular expression, DFSM, or NDFSM.
30. The intersection of CFL and regular language
Show me the answer
Answer: 2. Both (A) and (C) above
Explanation:
The intersection of a context-free language (CFL) and a regular language is always context-free.
31. Context-sensitive Grammar can be recognized by
Deterministic pushdown Automata
Non-deterministic pushdown automata
Finite State Machine (FSM)
Linearly Bounded Memory Machine
Show me the answer
Answer: 4. Linearly Bounded Memory Machine
Explanation:
Context-sensitive grammars are recognized by linearly bounded memory machines.
32. Which of the following regular expression identity's are true?
Show me the answer
Context-sensitive language
Recursively enumerable language
Show me the answer
Answer: 2. Context-free language
Explanation:
34. Consider the production grammar
Show me the answer
35. Which of the following sentences is generated by production grammar?
Show me the answer
Answer: 2. aabccd
Explanation:
36. Consider a NDFA shown in figure below. The Automation accepts
All words that contain the substring ab and end with a
All words that contain the substring ba and end with a
All words that end with a, and also the null string
Show me the answer
37. Which of the following is accepted by deterministic pushdown machine but not accepted by non-deterministic pushdown machine (NDPDM)?
Strings end with a particular alphabet
All strings in which a given symbol is present at least twice
Show me the answer
Answer: 3. Even palindrome
Explanation:
Even palindromes are accepted by deterministic pushdown machines but not by non-deterministic ones.
38. Consider the following grammar
Show me the answer
39. Which of the following instance of the post correspondence problem have a viable sequence?
Show me the answer
40. Which of the following statement(s) is (are) correct?
Recursively languages are closed under complementation
If a language and its complement are both recursively enumerable then language is recursive
Set of recursively enumerable language is closed under union
Show me the answer
Answer: 4. All of these
Explanation:
All the statements are correct regarding recursively enumerable languages.
41. Consider the following FA shown in figure below. The language accepted by the FA is
Show me the answer
42. Which of the following statement is wrong
Any regular language has an equivalent context-free grammar
Some non-regular languages can't be generated by any context-free grammar
The intersection of context free languages and a regular language is always context-free
All language can be generated by CFG
Show me the answer
Answer: 4. All language can be generated by CFG
Explanation:
Not all languages can be generated by context-free grammars (CFGs).
43. Consider a grammar
Context sensitive language
Recursively enumerable language
Show me the answer
Answer: 4. Recursively enumerable language
Explanation:
The grammar generates a recursively enumerable language.
44. The language constructs which are useful in describing nested structures such as balanced parenthesis
Non-context free grammars
Show me the answer
Answer: 3. Context-free grammar
Explanation:
Context-free grammars are used to describe nested structures like balanced parentheses.
45. A grammar that produce more than one parse free for same sentence is called
Show me the answer
Answer: 1. Ambiguous
Explanation:
A grammar that produces more than one parse tree for the same sentence is ambiguous.
Show me the answer
47. Palindromes can't be recognized by any Finite State Machine because
An FSM can't remember arbitrarily large amount of information
An FSM can't fix the mid-point
FSM can't find whether the second half of the string matches the first half
Show me the answer
Answer: 4. All of these
Explanation:
Finite State Machines (FSMs) cannot recognize palindromes due to their inability to remember large amounts of information and determine mid-points.
Show me the answer
Answer: 4. Right-linear
Explanation:
A language accepted by a finite automaton (FA) is right-linear.
Show me the answer
Answer: 4. xy xyx
Explanation:
50. Can a DFA simulate NFA?
Show me the answer
Answer: 3. Yes
Explanation:
A Deterministic Finite Automaton (DFA) can simulate a Non-deterministic Finite Automaton (NFA).
L={aib2j/i≥1}
{S→aSbb,S→abb}
{S→aA,S→b,A→b}
{S→aSb,S→b}
Answer: 1. {S→aSbb,S→abb}
The grammar generates strings with aib2j where i≥1.
L={aib2j/i≥1}
The string aaaabbbbbb fits the pattern aib2j with i=4 and j=3.
5. Give a production grammar for the language
L={x/x∈(a,b)∗, the number of
a’s in
x is multiple of 3}
{S→bS,S→b,S→aA,S→bA,A→aB,B→bB,B→aS,S→a}
{S→aS,S→bA,A→bB,B→bBa,B→bB}
{S→aaS,S→bbA,A→bB,B→ba}
Answer: 1. {S→bS,S→b,S→aA,S→bA,A→aB,B→bB,B→aS,S→a}
The grammar ensures that the number of a’s in the string is a multiple of 3.
6. Let
L1={ab/i>j} and
L2={ab/i<j}: the union of
L1 and
L2 is given by
{ab/i,j≥1}
ab/i>j≥1}
{ab/i,j≥1}
{ab/i,j≥1,i=j}
Answer: 4. {ab/i,j≥1,i=j}
The union of L1 and L2 includes all strings where i=j.
L={ab/I,j≥1,i=j}
{S→aS,S→aB,B→ab,A→aaB,B→b}
{S→A,S→C,A→aA,A→aB,B→aBb,B→ab,C→Cb,E→Bb}
{S→A,A→aA,A→aB,B→ab}
Answer: 2. {S→A,S→C,A→aA,A→aB,B→aBb,B→ab,C→Cb,E→Bb}
The grammar generates strings where the number of a’s and b’s are not equal.
8. The production grammar is
{S→aSbb,S→abb} is
The number of symbols unnecessary to simulate a Turing Machine (TM) with m symbols and n states is mn
14. Regular expression
(x/y) denotes the set
{xx,xy,yx,yy}
{x,y,xy}
Answer: 2. {x,y}
The regular expression (x/y) represents the set {x,y}.
15. Regular expression
x/y denotes the set
Answer: 1. {x,y}
The regular expression x/y represents the set {x,y}.
16. The regular expressions denote a language comprising all possible strings of even length over the alphabet
{0,1}
1+0(1+0)∗
(0+1)(1+0)∗
(00+011+10)∗
Answer: 4. (00+011+10)∗
The regular expression (00+011+10)∗ generates all strings of even length over {0,1}.
17. The regular expressions denote zero or more instances of an
x or
y is
Answer: 3. (x+y)∗
The regular expression (x+y)∗ denotes zero or more instances of x or y.
(0+1+2)∗
(0+1)∗2∗
Answer: 3. 0∗1∗2∗
The regular expression 0∗1∗2∗ generates strings with any number of 0's, followed by any number of 1's, followed by any number of 2's.
(0+ϵ)(1+10)∗
(0+1)∗011
Answer: 2. (0+ϵ)(1+10)∗
The regular expression (0+ϵ)(1+10)∗ ensures no two consecutive 0's.
(0+1)0(0+1)∗
Answer: 3. (0+1)0(0+1)∗
The regular expression (0+1)0(0+1)∗ generates strings with at least two consecutive 0's.
21. Which of the following is NOT the set of regular expression
R=(ab+abb)∗bbab
The string abababab does not fit the pattern (ab+abb)∗bbab.
S→aS/bA,A→d/cA
The string aabccd can be generated by the given grammar.
27. Let
L be a Language recognizable by Finite automation. The Language REVERSE
L′={ω/ω is the reverse of
v where
v∈L} is
28. The Grammar
G=<{S},{0,1},P,S> Where
p is
S→0SI,S→0S,S→SI,S→0 is
rS′=r+S
(r+S)′=r′+S′
Answer: 1. r′=r
The identity r′=r is true for regular expressions.
33. The Language
L={0:1n2k3k where n,k>0}
The language L is context-free as it can be generated by a context-free grammar.
S→XY/XS
X→a/aX
Y→b
Which of the following regular expressions corresponding to the production grammar?
The grammar generates strings of the form aab.
S→aSbX
X→dccX
The string aabccd can be generated by the given grammar.
All words that end with a, but not the null string ϵ
Answer: 3. All words that end with a, but not the null string ϵ
The NDFA accepts words ending with a but not the null string.
X→Xx/Yy
X→Yy/Zω
Y→y/Yw
Z→y
Which of the regular expressions describe the same set of strings as the grammar?
xωy+xωyx+yωx
xωy+xωxy+yωx
xωy+xωxyx+yωx+yωx
xωxy+xωωy+yωx
Answer: 1. xωy+xωyx+yωx
The regular expression xωy+xωyx+yωx matches the strings generated by the grammar.
{(x,xx),(xx,xyx),(xyx,yxx),(yyxx,xyyx)}
{(yx,yxy),(xyy,yy),(yyxy,yyy)}
{(yx,yxx),(xy,yyy),(yy,y)}
Answer: 3. {(yx,yxx),(xy,yyy),(yy,y)}
The instance {(yx,yxx),(xy,yyy),(yy,y)} has a viable sequence.
(a+b)∗b
(a+b)∗b
Answer: 2. (a+b)∗b
The FA accepts all strings ending with b.
S→SS
S→0S1
S→1S0
S→ϵ
The grammar will generate
46. Which of the regular expression denotes a language containing all possible strings over the alphabet
{a,b}?
Answer: 4. (a+b)∗
The regular expression (a+b)∗ denotes all possible strings over {a,b}.
48. A language
L is accepted by FA if and only if it is
49. A language is denoted by a regular expression
L={x∗(x/y)x}. Which of the following is not a legal string within
L?
The string xyxyx does not fit the pattern x∗(x/y)x.