R1∪R2R_1 \cup R_2R1∪R2 is regular
∑∩R2\sum \cap R_2∑∩R2is not regular
R1∩R2R_1 \cap R_2R1∩R2 is not regular
R2R_2R2 is not regular
Answer: 1. R1∪R2R_1 \cup R_2R1∪R2 is regular
Explanation:
The union of two regular sets is also regular.
S→AAS \rightarrow AAS→AA A→aaA \rightarrow aaA→aa A→bbA \rightarrow bbA→bb
Describe the language specified by the production grammar
L={aaaa,aabb,bbaa,bbbb}L = \{aaaa, aabb, bbaa, bbbb\}L={aaaa,aabb,bbaa,bbbb}
L={abab,abaa,aaab,baaa}L = \{abab, abaa, aaab, baaa\}L={abab,abaa,aaab,baaa}
L={aaab,baba,bbaa,bbbb}L = \{aaab, baba, bbaa, bbbb\}L={aaab,baba,bbaa,bbbb}
L={aaaa,ababa,bbaa,aaab}L = \{aaaa, ababa, bbaa, aaab\}L={aaaa,ababa,bbaa,aaab}
Answer: 1. L={aaaa,aabb,bbaa,bbbb}L = \{aaaa, aabb, bbaa, bbbb\}L={aaaa,aabb,bbaa,bbbb}
The grammar generates strings of even length with aaa and bbb.
L={aib2j/i≥1}L = \{a^i b^{2j} / i \geq 1\}L={aib2j/i≥1}
{S→aSbb,S→abb}\{S \rightarrow aSbb, S \rightarrow abb\}{S→aSbb,S→abb}
{S→aA,S→b,A→b}\{S \rightarrow aA, S \rightarrow b, A \rightarrow b\}{S→aA,S→b,A→b}
{S→aSb,S→b}\{S \rightarrow aSb, S \rightarrow b\}{S→aSb,S→b}
None of the above
Answer: 1. {S→aSbb,S→abb}\{S \rightarrow aSbb, S \rightarrow abb\}{S→aSbb,S→abb}
The grammar generates strings with aib2ja^i b^{2j}aib2j where i≥1i \geq 1i≥1.
Aaabbbbbb
Abbabbba
aabb
aaaabbbbbb
Answer: 4. aaaabbbbbb
The string aaaabbbbbbaaaabbbbbbaaaabbbbbb fits the pattern aib2ja^i b^{2j}aib2j with i=4i = 4i=4 and j=3j = 3j=3.
{S→bS,S→b,S→aA,S→bA,A→aB,B→bB,B→aS,S→a}\{S \rightarrow bS, S \rightarrow b, S \rightarrow aA, S \rightarrow bA, A \rightarrow aB, B \rightarrow bB, B \rightarrow aS, S \rightarrow a\}{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 \rightarrow aS, S \rightarrow bA, A \rightarrow bB, B \rightarrow bBa, B \rightarrow bB\}{S→aS,S→bA,A→bB,B→bBa,B→bB}
{S→aaS,S→bbA,A→bB,B→ba}\{S \rightarrow aaS, S \rightarrow bbA, A \rightarrow bB, B \rightarrow ba\}{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}\{S \rightarrow bS, S \rightarrow b, S \rightarrow aA, S \rightarrow bA, A \rightarrow aB, B \rightarrow bB, B \rightarrow aS, S \rightarrow a\}{S→bS,S→b,S→aA,S→bA,A→aB,B→bB,B→aS,S→a}
The grammar ensures that the number of aaa’s in the string is a multiple of 3.
{ab/i,j≥1}\{a^b / i, j \geq 1\}{ab/i,j≥1}
ab/i>j≥1}a^b / i > j \geq 1\}ab/i>j≥1}
{ab/i,j≥1,i≠j}\{a^b / i, j \geq 1, i \neq j\}{ab/i,j≥1,i=j}
Answer: 4. {ab/i,j≥1,i≠j}\{a^b / i, j \geq 1, i \neq j\}{ab/i,j≥1,i=j}
The union of L1L1L1 and L2L2L2 includes all strings where i≠ji \neq ji=j.
L={ab/I,j≥1,i≠j}L = \{a^b / I, j \geq 1, i \neq j\}L={ab/I,j≥1,i=j}
{S→aS,S→aB,B→ab,A→aaB,B→b}\{S \rightarrow aS, S \rightarrow aB, B \rightarrow ab, A \rightarrow aaB, B \rightarrow b\}{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 \rightarrow A, S \rightarrow C, A \rightarrow aA, A \rightarrow aB, B \rightarrow aBb, B \rightarrow ab, C \rightarrow Cb, E \rightarrow Bb\}{S→A,S→C,A→aA,A→aB,B→aBb,B→ab,C→Cb,E→Bb}
{S→A,A→aA,A→aB,B→ab}\{S \rightarrow A, A \rightarrow aA, A \rightarrow aB, B \rightarrow ab\}{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}\{S \rightarrow A, S \rightarrow C, A \rightarrow aA, A \rightarrow aB, B \rightarrow aBb, B \rightarrow ab, C \rightarrow Cb, E \rightarrow Bb\}{S→A,S→C,A→aA,A→aB,B→aBb,B→ab,C→Cb,E→Bb}
The grammar generates strings where the number of aaa’s and bbb’s are not equal.
Type-3 grammar
Type-1 grammar
Type-0 grammar
Answer: 3. Type-3 grammar
The grammar is a regular (Type-3) grammar as it generates regular languages.
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
Answer: 3. A finite State Machine with 2 stacks
A finite state machine cannot have 2 stacks; it is a characteristic of a pushdown automaton.
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
Answer: 4. A language is accepted by FA if and only if it is recursive
A language accepted by a finite automaton (FA) is regular, not necessarily recursive.
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
Answer: 2. A language is accepted by FA if and only if it is context free
A language accepted by a finite automaton (FA) is regular, not necessarily context-free.
All language can be generated by CFG
The number of symbols unnecessary to simulate a Turing Machine (TM) with mmm symbols and nnn states is mnmnmn
Any regular language has an equivalent CFG
The class of CFG is not closed under union
Answer: 3. Any regular language has an equivalent CFG
Every regular language can be represented by a context-free grammar (CFG).
Complementation
Intersection
Union
Answer: 1. Complementation
Recursively enumerable languages are not closed under complementation.
{xy,xy}\{xy, xy\}{xy,xy}
{x,y}\{x,y\}{x,y}
{xx,xy,yx,yy}\{xx,xy,yx,yy\}{xx,xy,yx,yy}
{x,y,xy}\{x,y,xy\}{x,y,xy}
Answer: 2. {x,y}\{x,y\}{x,y}
The regular expression (x/y)(x/y)(x/y) represents the set {x,y}\{x, y\}{x,y}.
{xy}\{xy\}{xy}
{x}\{x\}{x}
{y}\{y\}{y}
Answer: 1. {x,y}\{x,y\}{x,y}
The regular expression x/yx/yx/y represents the set {x,y}\{x, y\}{x,y}.
1+0(1+0)∗1 + 0 (1 + 0)^*1+0(1+0)∗
(1+0)(1 + 0)(1+0)
(0+1)(1+0)∗(0 + 1) (1 + 0)^*(0+1)(1+0)∗
(00+011+10)∗(00 + 011 + 10)^*(00+011+10)∗
Answer: 4. (00+011+10)∗(00 + 011 + 10)^*(00+011+10)∗
The regular expression (00+011+10)∗(00 + 011 + 10)^*(00+011+10)∗ generates all strings of even length over {0,1}\{0,1\}{0,1}.
(x+y)(x + y)(x+y)
(x∗+y)(x^* + y)(x∗+y)
(x+y)∗(x + y)^*(x+y)∗
(xy)∗(xy)^*(xy)∗
Answer: 3. (x+y)∗(x + y)^*(x+y)∗
The regular expression (x+y)∗(x + y)^*(x+y)∗ denotes zero or more instances of xxx or yyy.
(0+1+2)∗(0 + 1 + 2)^*(0+1+2)∗
0∗+1+20^* + 1 + 20∗+1+2
0∗1∗2∗0^* 1^* 2^*0∗1∗2∗
(0+1)∗2∗(0 + 1)^* 2^*(0+1)∗2∗
Answer: 3. 0∗1∗2∗0^* 1^* 2^*0∗1∗2∗
The regular expression 0∗1∗2∗0^* 1^* 2^*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)(0 + 1)(0+1)
(0+ϵ)(1+10)∗(0 + \epsilon) (1 + 10)^*(0+ϵ)(1+10)∗
(0+1)∗(0 + 1)^*(0+1)∗
(0+1)∗011(0 + 1)^* 011(0+1)∗011
Answer: 2. (0+ϵ)(1+10)∗(0 + \epsilon) (1 + 10)^*(0+ϵ)(1+10)∗
The regular expression (0+ϵ)(1+10)∗(0 + \epsilon) (1 + 10)^*(0+ϵ)(1+10)∗ ensures no two consecutive 0's.
1+(10)∗1 + (10)^*1+(10)∗
(0+1)0(0 + 1)^0(0+1)0
(0+1)0(0+1)∗(0 + 1)^0(0 + 1)^*(0+1)0(0+1)∗
010^101
Answer: 3. (0+1)0(0+1)∗(0 + 1)^0(0 + 1)^*(0+1)0(0+1)∗
The regular expression (0+1)0(0+1)∗(0 + 1)^0(0 + 1)^*(0+1)0(0+1)∗ generates strings with at least two consecutive 0's.
Ababbbbab
Ababbabbbbab
Abbbab
Abababab
Answer: 4. Abababab
The string abababababababababababab does not fit the pattern (ab+abb)∗bbab(ab + abb)^*bbab(ab+abb)∗bbab.
S→aS/bA,A→d/cAS \rightarrow aS/bA, A \rightarrow d/cAS→aS/bA,A→d/cA
Aabccd
Abcca
Adabcca
Abababd
Answer: 1. Aabccd
The string aabccdaabccdaabccd can be generated by the given grammar.
Kleene's closure
Concentration
All of the above
Answer: 4. All of the above
Regular sets are closed under union, Kleene's closure, and concatenation.
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
Answer: 4. Context sensitive Grammar (CGS) can be recognized by Finite State Machine
Context-sensitive grammars cannot be recognized by finite state machines.
Turing machine
Context free languages
Pushdown automata
Regular language
Answer: 1. Turing machine
A finite state machine with finite tape length and unidirectional tape movement behaves like a Turing machine.
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
Answer: 4. Turing machine is more powerful than FMS because it has no final state
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-free language
Context-sensitive language
Recursively enumerable language
Answer: 1. Regular language
The reverse of a regular language is also regular.
Regular expression
Context free language
Answer: 4. Context free language
The grammar is context-free as it generates a context-free language.
DFSM (Deterministic Finite State Machine)
NDFSM
All of them
Answer: 4. All of them
A transition graph can be converted into a regular expression, DFSM, or NDFSM.
Is always regular
Both (A) and (C) above
Is always context-free
Need not be regular
Answer: 2. Both (A) and (C) above
The intersection of a context-free language (CFL) and a regular language is always context-free.
Deterministic pushdown Automata
Non-deterministic pushdown automata
Finite State Machine (FSM)
Linearly Bounded Memory Machine
Answer: 4. Linearly Bounded Memory Machine
Context-sensitive grammars are recognized by linearly bounded memory machines.
r′=rr' = rr′=r
rS′=r+SrS' = r + SrS′=r+S
(r+S)′=r′+S′(r + S)' = r' + S'(r+S)′=r′+S′
All of these
Answer: 1. r′=rr' = rr′=r
The identity r′=rr' = rr′=r is true for regular expressions.
Regular languages
Answer: 2. Context-free language
The language LLL is context-free as it can be generated by a context-free grammar.
S→XY/XSS \rightarrow XY/XSS→XY/XS X→a/aXX \rightarrow a/aXX→a/aX Y→bY \rightarrow bY→b Which of the following regular expressions corresponding to the production grammar?
(ab)(ab)(ab)
a(ab)ba(ab)^{b}a(ab)b
aabba^a b^baabb
aaba^a baab
Answer: 4. aaba^a baab
The grammar generates strings of the form aaba^a baab.
S→aSbXS \rightarrow aSbXS→aSbX X→dccXX \rightarrow dccXX→dccX
Abblod
aabccd
aabd
ababccd
Answer: 2. aabccd
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, but not the null string ϵ\epsilonϵ
All words that end with a, and also the null string
Answer: 3. All words that end with a, but not the null string ϵ\epsilonϵ
The NDFA accepts words ending with aaa but not the null string.
Strings end with a particular alphabet
All strings in which a given symbol is present at least twice
Even palindrome
None of these
Answer: 3. Even palindrome
Even palindromes are accepted by deterministic pushdown machines but not by non-deterministic ones.
X→Xx/YyX \rightarrow Xx/YyX→Xx/Yy X→Yy/ZωX \rightarrow Yy/Z\omegaX→Yy/Zω Y→y/YwY \rightarrow y/YwY→y/Yw Z→yZ \rightarrow yZ→y Which of the regular expressions describe the same set of strings as the grammar?
xωy+xωyx+yωxx\omega y + x\omega yx + y\omega xxωy+xωyx+yωx
xωy+xωxy+yωxx\omega y + x\omega xy + y\omega xxωy+xωxy+yωx
xωy+xωxyx+yωx+yωxx\omega y + x\omega xyx + y\omega x + y\omega xxωy+xωxyx+yωx+yωx
xωxy+xωωy+yωxx\omega xy + x\omega \omega y + y\omega xxωxy+xωωy+yωx
Answer: 1. xωy+xωyx+yωxx\omega y + x\omega yx + y\omega xxωy+xωyx+yωx
The regular expression xωy+xωyx+yωxx\omega y + x\omega yx + y\omega xxωy+xωyx+yωx matches the strings generated by the grammar.
{(x,xx),(xx,xyx),(xyx,yxx),(yyxx,xyyx)}\{(x, xx), (xx, xyx), (xyx, yxx), (yyxx, xyyx)\}{(x,xx),(xx,xyx),(xyx,yxx),(yyxx,xyyx)}
{(yx,yxy),(xyy,yy),(yyxy,yyy)}\{(yx, yxy), (xyy, yy), (yyxy, yyy)\}{(yx,yxy),(xyy,yy),(yyxy,yyy)}
{(yx,yxx),(xy,yyy),(yy,y)}\{(yx, yxx), (xy, yyy), (yy, y)\}{(yx,yxx),(xy,yyy),(yy,y)}
Answer: 3. {(yx,yxx),(xy,yyy),(yy,y)}\{(yx, yxx), (xy, yyy), (yy, y)\}{(yx,yxx),(xy,yyy),(yy,y)}
The instance {(yx,yxx),(xy,yyy),(yy,y)}\{(yx, yxx), (xy, yyy), (yy, y)\}{(yx,yxx),(xy,yyy),(yy,y)} has a viable sequence.
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
Answer: 4. All of these
All the statements are correct regarding recursively enumerable languages.
(a+b)∗b(a + b)^* b(a+b)∗b
a∗ba^* ba∗b
Answer: 2. (a+b)∗b(a + b)^* b(a+b)∗b
The FA accepts all strings ending with bbb.
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
Answer: 4. All language can be generated by CFG
Not all languages can be generated by context-free grammars (CFGs).
S→SSS \rightarrow SSS→SS S→0S1S \rightarrow 0S1S→0S1 S→1S0S \rightarrow 1S0S→1S0 S→ϵS \rightarrow \epsilonS→ϵ The grammar will generate
Context sensitive language
Answer: 4. Recursively enumerable language
The grammar generates a recursively enumerable language.
Non-context free grammars
Context-free grammar
Answer: 3. Context-free grammar
Context-free grammars are used to describe nested structures like balanced parentheses.
Ambiguous
Regular
Unambiguous
Answer: 1. Ambiguous
A grammar that produces more than one parse tree for the same sentence is ambiguous.
a∗b∗a^* b^*a∗b∗
(a,b)∗(a, b)^*(a,b)∗
(ab)∗(ab)^*(ab)∗
(a+b)∗(a + b)^*(a+b)∗
Answer: 4. (a+b)∗(a + b)^*(a+b)∗
The regular expression (a+b)∗(a + b)^*(a+b)∗ denotes all possible strings over {a,b}\{a, b\}{a,b}.
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
Finite State Machines (FSMs) cannot recognize palindromes due to their inability to remember large amounts of information and determine mid-points.
Context-free
Recursive
Context sensitive
Right-linear
Answer: 4. Right-linear
A language accepted by a finite automaton (FA) is right-linear.
Yx
yxx
x
xy xyx
Answer: 4. xy xyx
The string xyxyxxy xyxxyxyx does not fit the pattern x∗(x/y)xx^*(x/y)xx∗(x/y)x.
No
Sometimes
Yes
Depends on NFA
Answer: 3. Yes
A Deterministic Finite Automaton (DFA) can simulate a Non-deterministic Finite Automaton (NFA).
