> For the complete documentation index, see [llms.txt](https://nec-license.gitbook.io/books/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nec-license.gitbook.io/books/6.-theory-of-computation-and-computer-graphics/mcqs/mcqs-on-theory-of-computation/set-3.md).
# set-3
#### 101. The set $$A = {a^n b^n c^n / n = 1, 2, 3, \ldots}$$ is an example of
1. Regular language
2. Non context free language
3. Context free language
4. None of these
Show me the answer
**Answer:** 2. Non context free language
**Explanation:**
* The language $$A = {a^n b^n c^n / n = 1, 2, 3, \ldots}$$ is not context-free as it requires matching counts of $$a$$'s, $$b$$'s, and $$c$$'s.
#### 102. The intersection of CFL and a regular language
1. Need not be regular
2. Is always regular
3. Need not be context free
4. None of these
Show me the answer
**Answer:** 2. Is always regular
**Explanation:**
* The intersection of a context-free language (CFL) and a regular language is always context-free.
#### 103. Choose the correct statements:
1. The power of DFSM and NDFSM are same.
2. The power of DFSM and NDFSM are different.
3. The power of DPDM and NDPDM are different.
4. Both (A) and (C) above.
Show me the answer
**Answer:** 4. Both (A) and (C) above.
**Explanation:**
* Deterministic and non-deterministic finite state machines (DFSM and NDFSM) are equivalent in power, while deterministic and non-deterministic pushdown automata (DPDM and NDPDM) are not.
#### 104. Which of the following is accepted by an NDPDM but not by a DPDM?
1. All strings in which a given symbol is present at least twice
2. Even palindromes.
3. Strings ending with a particular alphabet.
4. None of these.
Show me the answer
**Answer:** 2. Even palindromes.
**Explanation:**
* Even palindromes are accepted by non-deterministic pushdown automata (NDPDM) but not by deterministic pushdown automata (DPDM).
#### 105. Bounded minimization is a technique for
1. Proving whether a promotive recursive function is Turing computable or not.
2. Providing whether a primitive recursive function is a total function or not.
3. Generating primitive recursive functions.
4. Generating partial recursive functions.
Show me the answer
**Answer:** 3. Generating primitive recursive functions.
**Explanation:**
* Bounded minimization is used to generate primitive recursive functions.
#### 106. Universal Turing machine influenced the concept of
1. Stored program computers
2. Interpretive implementation of programming language
3. Computability
4. All of these
Show me the answer
**Answer:** 4. All of these
**Explanation:**
* The Universal Turing Machine influenced the concepts of stored program computers, interpretive implementation of programming languages, and computability.
#### 107. The statement "A Turing machine can't solve halting problem" is
1. True
2. Still at open question
3. False
4. All of these
Show me the answer
**Answer:** 1. True
**Explanation:**
* The halting problem is undecidable, meaning no Turing machine can solve it.
#### 108. If there exists a TM which when applied to any problem in the class, terminates, if the correct answer is yes and may or may not terminate otherwise is said to be
1. Stable
2. Partially solvable
3. Unstable
4. Unstable
Show me the answer
**Answer:** 2. Partially solvable
**Explanation:**
* A problem is partially solvable if a Turing machine terminates for "yes" instances but may not terminate for "no" instances.
#### 109. The vernacular language English, if considered a formal language is a
1. Regular language
2. Context sensitive language
3. Context free language
4. None of these
Show me the answer
**Answer:** 3. Context free language
**Explanation:**
* English, as a formal language, is context-free.
#### 110. P, Q, R are three languages, if P and R are regular and if PQ = R then
1. Q = R
2. Both A and B
3. Q = P
4. None of these
Show me the answer
**Answer:** 4. None of these
**Explanation:**
* The relationship between P, Q, and R cannot be determined from the given information.
#### 111. Consider the grammar
$$S \rightarrow PQ/SQ/PS$$\
$$P \rightarrow X,$$\
$$Q \rightarrow Y$$\
To get string of n terminals, the number of productions to be used is
1. N
2. n + 1
3. 2^n
4. 2^{n-1}
Show me the answer
**Answer:** 4. 2^{n-1}
**Explanation:**
* The number of productions required to generate a string of $$n$$ terminals is $$2^{n-1}$$.
#### 112. The following grammar
$$S \rightarrow aab/bac/ab$$\
$$S \rightarrow abb/ab$$\
$$S \rightarrow aS/b$$\
$$B \rightarrow bab/b$$
1. CFG
2. Context sensitive
3. Regular
4. None of these
Show me the answer
**Answer:** 2. Context sensitive
**Explanation:**
* The grammar is context-sensitive as it allows for context-dependent productions.
#### 113. Let $$A = {0,1}$$ and $$L = A^\*$$. Let $$R = {0^n, n > 0}$$ then the language $$L \cup R$$ and $$R$$ are respectively.
1. Regular, regular
2. Regular, not regular
3. Not regular, regular
4. Not regular, not regular
Show me the answer
**Answer:** 2. Regular, not regular
**Explanation:**
* $$L \cup R$$ is regular, while $$R$$ is not regular.
#### 114. Which of the following is not possible algorithmically?
1. Regular grammar to context free grammar
2. Non-deterministic finite state Automata to deterministic FSA
3. Non-deterministic PDA to deterministic PDA
4. None of these
Show me the answer
**Answer:** 3. Non-deterministic PDA to deterministic PDA
**Explanation:**
* Converting a non-deterministic PDA to a deterministic PDA is not always possible algorithmically.
#### 115. As FSM can be used to add two given integers. That is
1. True
2. False
3. May be true
4. None of these
Show me the answer
**Answer:** 2. False
**Explanation:**
* Finite state machines (FSMs) cannot perform arithmetic operations like addition.
#### 116. A grammar is said to be in CNF, if all the productions are of the form $$A \rightarrow BC$$ or $$A \rightarrow a$$. Let $$G$$ be a CFG in CNF. To derive a string of terminals of length $$x$$, the number of production to be used is
1. $$2x - 1$$
2. $$2x$$
3. $$2x + 1$$
4. $$2^x$$
Show me the answer
**Answer:** 1. $$2x - 1$$
**Explanation:**
* In Chomsky Normal Form (CNF), deriving a string of length $$x$$ requires $$2x - 1$$ productions.
#### 117. In given fig
1. Both are equivalent
2. The first FSM accepts nothing
3. The second FSM accepts $$\epsilon$$-only
4. None of these
Show me the answer
**Answer:** 4. None of these
**Explanation:**
* The given FSMs are not equivalent, and neither accepts only $$\epsilon$$.
#### 118. The number of tokens in the Fortran statement DO 10 I = 1.25 is
1. 3
2. 4
3. 5
4. None of these
Show me the answer
**Answer:** 4. None of these
**Explanation:**
* The number of tokens in the statement is 6.
#### 119. The word 'formal' in formal languages means
1. The symbols used have well-defined language meaning
2. They are unnecessary in reality
3. Only the form of the string of symbols is significant
4. None of these
Show me the answer
**Answer:** 3. Only the form of the string of symbols is significant
**Explanation:**
* In formal languages, the structure (form) of the string is significant, not the meaning.
#### 120. If $$A = {0, 1}$$, the number of possible strings of length 'n' is
1. $$n!$$
2. $$n \times n$$
3. $$n^n$$
4. $$2^n$$
Show me the answer
**Answer:** 4. $$2^n$$
**Explanation:**
* For alphabet $$A = {0, 1}$$, the number of possible strings of length $$n$$ is $$2^n$$.
#### 121. A mealy machine
1. May be machine
2. Has an equivalent more
3. Only context-free grammar
4. All of these
Show me the answer
**Answer:** 2. Has an equivalent more
**Explanation:**
* A Mealy machine has an equivalent Moore machine.
#### 122. The recognizing capability of NDFSM and DFSM
1. May be different
2. Must be same
3. Must be different
4. None of these
Show me the answer
**Answer:** 2. Must be same
**Explanation:**
* Non-deterministic finite state machines (NDFSM) and deterministic finite state machines (DFSM) have the same recognizing capability.
#### 123. Which of the following are not regular
1. String of 0's whose length is a perfect square
2. Set of all palindromes made up of 0's and 1's
3. Strings of 0's, whose length is a prime number
4. All of these
Show me the answer
**Answer:** 4. All of these
**Explanation:**
* None of the given languages are regular.
#### 124. Which of the following pairs of regular expressions are equivalent?
1. $$1(01)^*$$ and $$(10)^*$$
2. $$y^+$$ and $$y^\*y^+$$
3. $$Y(yy)^\*$$ and $$(yy)^\*y$$
4. All of these
Show me the answer
**Answer:** 4. All of these
**Explanation:**
* All the given pairs of regular expressions are equivalent.
#### 125. The logic of pumping Lemma is a good example of
1. The pigeon-hole principle
2. The divide and conquer technique
3. Recursion
4. Iteration
Show me the answer
**Answer:** 1. The pigeon-hole principle
**Explanation:**
* The Pumping Lemma is based on the pigeon-hole principle.
#### 126. The FSM pictured shown in the figure
1. Mealy machine
2. Kleene machine
3. Moore machine
4. None of these
Show me the answer
**Answer:** 1. Mealy machine
**Explanation:**
* The FSM represents a Mealy machine as its output depends on both the current state and input.
#### 127. The above machine
1. Complements a given bit pattern
2. Generates all strings of 0's and 1's
3. Adds 1 to a given bit pattern
4. None of these
Show me the answer
**Answer:** 1. Complements a given bit pattern
**Explanation:**
* The machine complements a given bit pattern.
#### 128. The language of all words with at least 2a's can be described by the regular expression
1. $$(a + b)^\*a(a + b)^*a(a + b)^*$$
2. $$b^\*a^\*b^*a(a + b)^*$$
3. $$(a + b)^\*ab^*a(a + b)^*$$
4. All of these
Show me the answer
**Answer:** 4. All of these
**Explanation:**
* All the given regular expressions describe the language of words with at least 2a's.
#### 129. For the following figure
1. Complements a given bit pattern
2. Finds 2's complement of a given bit pattern
3. Increment a given bit pattern by 1
4. Change the sign bit
Show me the answer
**Answer:** 3. Increment a given bit pattern by 1
**Explanation:**
* The machine increments a given bit pattern by 1.
#### 130. For which of the following applications regular expression can't be used?
1. Designing compilers
2. Simulating sequential circuits
3. Developing text editors
4. All of these
Show me the answer
**Answer:** 2. Simulating sequential circuits
**Explanation:**
* Regular expressions are not suitable for simulating sequential circuits.
#### 131. The following CFG
$$S \rightarrow xS/yS/x/y$$\
Is equivalent to the regular expression
1. $$(x + y)^\*$$
2. $$(x + y)^\*(x + y)$$
3. $$(x + y)(x + y)^\*$$
4. All of these
Show me the answer
**Answer:** 4. All of these
**Explanation:**
* The CFG is equivalent to all the given regular expressions.
#### 132. Any string of terminals that can be generated by the following CFG
$$S \rightarrow AB$$\
$$A \rightarrow aA/bB/a$$\
$$B \rightarrow Ba/Bb/a$$
1. Has at least one b
2. Has no consecutive a's or b's
3. Should end in an 'a'
4. Has at least two a's
Show me the answer
**Answer:** 4. Has at least two a's
**Explanation:**
* The CFG generates strings with at least two a's.
#### 133. The following CFG
$$S \rightarrow aB/bA$$\
$$A \rightarrow b/aS/bAA$$\
$$B \rightarrow b/bs/aBB$$\
Generates strings of terminals that have
1. Equal number of a's and b's
2. Odd number of a's and odd number of b's
3. Even number of a's and number of b's
4. Odd number a's and een number of a's
Show me the answer
**Answer:** 1. Equal number of a's and b's
**Explanation:**
* The CFG generates strings with an equal number of a's and b's.
#### 134. The set $${a^n b^n / n = 1, 2, \ldots}$$ can be generated by a CFG
1. $$S \rightarrow ab/aSb$$
2. $$S \rightarrow ab/aSb/\epsilon$$
3. $$S \rightarrow aSbb/ab$$
4. $$S \rightarrow aSbb/ab/aabb$$
Show me the answer
**Answer:** 1. $$S \rightarrow ab/aSb$$
**Explanation:**
* The CFG $$S \rightarrow ab/aSb$$ generates the set $${a^n b^n / n = 1, 2, \ldots}$$.
#### 135. Which of the following CFG's can't be simulated by an FSM?
1. $$S \rightarrow Sa/a$$
2. $$S \rightarrow a/X, X \rightarrow cY, Y \rightarrow -d/aX$$
3. $$S \rightarrow aSb/ab$$
4. None of these
Show me the answer
**Answer:** 3. $$S \rightarrow aSb/ab$$
**Explanation:**
* The CFG $$S \rightarrow aSb/ab$$ generates a non-regular language and cannot be simulated by an FSM.
#### 136. CFG is not closed under
1. Union
2. Complementation's
3. Kleene star
4. Product
Show me the answer
**Answer:** 2. Complementation's
**Explanation:**
* Context-free grammars (CFGs) are not closed under complementation.
#### 137. The set $$A = {a^n b^n c^n / n = 1, 2, 3, \ldots}$$ is an example of a grammar that is
1. Regular
2. Not context free
3. Context-free
4. None of these
Show me the answer
**Answer:** 2. Not context free
**Explanation:**
* The language $$A = {a^n b^n c^n / n = 1, 2, 3, \ldots}$$ is not context-free.
#### 138. Let
$$L\_1 = {a^n b^n a^m / n, m = 1, 2, 3, \ldots}$$\
$$L\_2 = {a^n b^m a^m / n, m = 1, 2, 3, \ldots}$$\
$$L\_3 = {a^n b^n c^n / n = 1, 2, 3, \ldots}$$\
Of the following the correct answer is
1. $$L\_3 = L\_1 \cap L\_2$$
2. $$L\_1$$ and $$L\_2$$ are not CFL, but $$L\_3$$ is CFL
3. $$L\_1$$ is a subset of $$L\_3$$
4. None of these
Show me the answer
**Answer:** 1. $$L\_3 = L\_1 \cap L\_2$$
**Explanation:**
* The language $$L\_3$$ is the intersection of $$L\_1$$ and $$L\_2$$.
#### 139. The intersection of a CFL, and a regular language
1. Need not be regular
2. Is always regular
3. Need not be context free
4. None of these
Show me the answer
**Answer:** 3. Need not be context free
**Explanation:**
* The intersection of a context-free language (CFL) and a regular language is always context-free.
#### 140. A PDM behave lie an FSM when the number of auxiliary memory it has is
1. 0
2. 1
3. 2
4. None of these
Show me the answer
**Answer:** 1. 0
**Explanation:**
* A pushdown automaton (PDM) behaves like a finite state machine (FSM) when it has no auxiliary memory (stack).
#### 141. CSG can be recognized by a
1. FSM
2. NDPDM
3. DPDM
4. Linearly bounded memory machine
Show me the answer
**Answer:** 4. Linearly bounded memory machine
**Explanation:**
* Context-sensitive grammars (CSG) are recognized by linearly bounded memory machines.
#### 142. An FSM with
1. A stack is more powerful than a FSM with no stack.
2. 2 stacks is more powerful than a FSM 1 stack
3. Both (A) and (B) above
4. None of these
Show me the answer
**Answer:** 3. Both (A) and (B) above
**Explanation:**
* Adding stacks to an FSM increases its computational power.
#### 143. Recursive languages are
1. Closed under intersection
2. Closed under complementation
3. Recursively enumerable
4. All of these
Show me the answer
**Answer:** 4. All of these
**Explanation:**
* Recursive languages are closed under intersection, complementation, and are recursively enumerable.
#### 144. If $$\omega \in (a, b)^\*$$ satisfy $$ab\omega = \omega ab$$ then $$'\omega'$$ is
1. Even
2. Odd
3. Null
4. None of these
Show me the answer
**Answer:** 1. Even
**Explanation:**
* The string $$\omega$$ must be even in length to satisfy the equation $$ab\omega = \omega ab$$.
#### 145. Let $$f : (a, b)^\* \rightarrow (a, b)^\*$$ be given by $$f(n) = ax$$ for every value of $$n \in {a, b}$$ then $$f$$ is
1. One to one not onto
2. Not one to one and not onto
3. One to one and onto
4. Not one to one and onto
Show me the answer
**Answer:** 1. One to one not onto
**Explanation:**
* The function $$f$$ is one-to-one but not onto.
#### 146. Let if $$G = ({S}, {a}, {S \rightarrow SS}, S)$$, find language generated by $$G$$
1. $$L(G) = \phi$$
2. $$L(G) = a^\*$$
3. $$L(G) = a^n$$
4. $$L(G) = a^n ba^n$$
Show me the answer
**Answer:** 2. $$L(G) = a^\*$$
**Explanation:**
* The grammar generates the language $$a^\*$$.
#### 147. What is the highest type number which can be applied to the following grammar
$$S \varphi \rightarrow Aa; A \rightarrow Ba, B \rightarrow abc$$
1. Type0
2. Type1
3. Type2
4. Type3
Show me the answer
**Answer:** 4. Type3
**Explanation:**
* The grammar is of Type 3 (regular grammar).
#### 148. Construct a grammar to generate $${(ab)^n / n \geq 1} \cup {(\text{ba})^n / n \geq 1}$$
1. $$S \rightarrow S\_1, S\_1 \rightarrow abS\_1, S\_1 \rightarrow ab, S \rightarrow S\_2, S\_2 \rightarrow baS\_2, S\_2 \rightarrow ba$$
2. $$S \rightarrow S\_1, S\_1 \rightarrow aS\_1, S\_1 \rightarrow ab, S \rightarrow S\_2, S\_2 \rightarrow bS\_2, S\_2 \rightarrow bc$$
3. $$S \rightarrow S\_1, S\_1 \rightarrow S\_2, S\_2 \rightarrow S\_1a, S\_1 \rightarrow ab, S\_2 \rightarrow ba$$
4. None of these
Show me the answer
**Answer:** 1. $$S \rightarrow S\_1, S\_1 \rightarrow abS\_1, S\_1 \rightarrow ab, S \rightarrow S\_2, S\_2 \rightarrow baS\_2, S\_2 \rightarrow ba$$
**Explanation:**
* The grammar generates the language $${(ab)^n / n \geq 1} \cup {(\text{ba})^n / n \geq 1}$$.
#### 149. Which string recognize it?
1. $$(a + b)^\*$$
2. $$a + b (a + bb)^\* (a + (b + aa)^*)^*$$
3. $$a^\*b (b + aa)^\*ba(b + aa)^\*a$$
4. Information is not complete
Show me the answer
**Answer:** 4. Information is not complete
**Explanation:**
* The question lacks sufficient information to determine the correct answer.
#### 150. Regular expression corresponding to the state diagram given in below figure
1. $$(0 + 1 (1 + 01) '00)'$$
2. $$(0 + 1 (1 + 10) 00)'$$
3. $$(1 + 0)(0 + 10) '00)'$$
4. $$(1 + 0 (1 + 00) 11)'$$
Show me the answer
**Answer:** 1. $$(0 + 1 (1 + 01) '00)'$$
**Explanation:**
* The regular expression $$(0 + 1 (1 + 01) '00)'$$ corresponds to the given state diagram.
#### 151. $$L = {a^p / p \text{ is a prime}}$$ is a
1. Regular
2. Accepted by DFA
3. Not regular
4. Accepted by PDA
Show me the answer
**Answer:** 3. Not regular
**Explanation:**
* The language $$L = {a^p / p \text{ is a prime}}$$ is not regular as it requires checking for primality, which cannot be done by a finite automaton.
#### 152. Regular expression corresponding to the automata given in figure below are:
1. $$1 (1 + 0 (0 + 10) '11)' 0 (0 + 10) '1$$
2. $$0 (1 + 0 (1 + 01) '11)' 1 (1 + 10) '1$$
3. $$1 (1 + 0 (1 + 01) '00)' 1 (1 + 01)'$$
4. $$0 (1 + 0 (1 + 01) '00)' 1 (1 + 01)' 1$$
Show me the answer
**Answer:** 1. $$1 (1 + 0 (0 + 10) '11)' 0 (0 + 10) '1$$
**Explanation:**
* The regular expression $$1 (1 + 0 (0 + 10) '11)' 0 (0 + 10) '1$$ corresponds to the given automaton.
#### 153. Grammar $$S \rightarrow aAb, A \rightarrow aAb/a$$ is in
1. LR(1) not in LR(0)
2. LR(0) but not in LR(1)
3. Both LR(0) and LR(1)
4. Neither LR(0) nor in LR(1)
Show me the answer
**Answer:** 1. LR(1) not in LR(0)
**Explanation:**
* The grammar is LR(1) but not LR(0).
#### 154. The language $$L = {a^n b^n c^n / n \geq 1}$$ is a
1. Regular language
2. Context-free language
3. Context-sensitive language
4. Recursively enumerable language
Show me the answer
**Answer:** 3. Context-sensitive language
**Explanation:**
* The language $$L = {a^n b^n c^n / n \geq 1}$$ is context-sensitive as it requires matching counts of $$a$$'s, $$b$$'s, and $$c$$'s.
#### 155. The set $${a^n b^n / n = 1, 2, 3, \ldots}$$ can be generated by the CFG
1. $$S \rightarrow ab/aSb$$
2. $$S \rightarrow ab/aSb/\epsilon$$
3. $$S \rightarrow aaSbb/ab$$
4. None of these
Show me the answer
**Answer:** 1. $$S \rightarrow ab/aSb$$
**Explanation:**
* The CFG $$S \rightarrow ab/aSb$$ generates the set $${a^n b^n / n = 1, 2, 3, \ldots}$$.
#### 156. Which of the following CFG's can't be simulated by an FSM?
1. $$S \rightarrow Sa/a$$
2. $$S \rightarrow abX, X \rightarrow cY, Y \rightarrow a/aX$$
3. $$S \rightarrow aSb/ab$$
4. None of these
Show me the answer
**Answer:** 3. $$S \rightarrow aSb/ab$$
**Explanation:**
* The CFG $$S \rightarrow aSb/ab$$ generates a non-regular language and cannot be simulated by an FSM.
#### 157. The set $$A = {a^n b^n c^n / n = 1, 2, 3, \ldots}$$ is an example of
1. Regular language
2. Non context free language
3. Context free language
4. None of these
Show me the answer
**Answer:** 2. Non context free language
**Explanation:**
* The language $$A = {a^n b^n c^n / n = 1, 2, 3, \ldots}$$ is not context-free.
#### 158. The intersection of CFL and a regular language
1. Need not be regular
2. Is always regular
3. Need not be context free
4. None of these
Show me the answer
**Answer:** 2. Is always regular
**Explanation:**
* The intersection of a context-free language (CFL) and a regular language is always context-free.
#### 159. Choose the correct statements:
1. The power of DFSM and NDFSM are same.
2. The power of DFSM and NDFSM are different.
3. The power of DPDM and NDPDM are different.
4. Both (A) and (C) above.
Show me the answer
**Answer:** 4. Both (A) and (C) above.
**Explanation:**
* Deterministic and non-deterministic finite state machines (DFSM and NDFSM) are equivalent in power, while deterministic and non-deterministic pushdown automata (DPDM and NDPDM) are not.
#### 160. Which of the following is accepted by an NDPDM but not by a DPDM?
1. All strings in which a given symbol is present at least twice
2. Even palindromes.
3. Strings ending with a particular alphabet.
4. None of these.
Show me the answer
**Answer:** 2. Even palindromes.
**Explanation:**
* Even palindromes are accepted by non-deterministic pushdown automata (NDPDM) but not by deterministic pushdown automata (DPDM).