Skip to Content
Live class going on, get early discount!
LicenseComputer6. Theory-of-computation-and-computer-graphicsMCQsMcqs on Theory of Computationset-1

set-1

1. Let R1R_1 and R2R_2 be regular sets defined over alphabet ∑\sum then

  1. R1∪R2R_1 \cup R_2 is regular
  2. ∑∩R2\sum \cap R_2is not regular
  3. R1∩R2R_1 \cap R_2 is not regular
  4. R2R_2 is not regular
Show me the answer

Answer: 1. R1∪R2R_1 \cup R_2 is regular

Explanation:

  • The union of two regular sets is also regular.

2. Consider the production of the grammar

S→AAS \rightarrow AA
A→aaA \rightarrow aa
A→bbA \rightarrow bb

Describe the language specified by the production grammar

  1. L={aaaa,aabb,bbaa,bbbb}L = \{aaaa, aabb, bbaa, bbbb\}
  2. L={abab,abaa,aaab,baaa}L = \{abab, abaa, aaab, baaa\}
  3. L={aaab,baba,bbaa,bbbb}L = \{aaab, baba, bbaa, bbbb\}
  4. L={aaaa,ababa,bbaa,aaab}L = \{aaaa, ababa, bbaa, aaab\}
Show me the answer

Answer: 1. L={aaaa,aabb,bbaa,bbbb}L = \{aaaa, aabb, bbaa, bbbb\}

Explanation:

  • The grammar generates strings of even length with aa and bb.

3. Give a production grammar that specifies the language

L={aib2j/i≥1}L = \{a^i b^{2j} / i \geq 1\}

  1. {S→aSbb,S→abb}\{S \rightarrow aSbb, S \rightarrow abb\}
  2. {S→aA,S→b,A→b}\{S \rightarrow aA, S \rightarrow b, A \rightarrow b\}
  3. {S→aSb,S→b}\{S \rightarrow aSb, S \rightarrow b\}
  4. None of the above
Show me the answer

Answer: 1. {S→aSbb,S→abb}\{S \rightarrow aSbb, S \rightarrow abb\}

Explanation:

  • The grammar generates strings with aib2ja^i b^{2j} where i≥1i \geq 1.

4. Which of the following string can be obtained by the language

L={aib2j/i≥1}L = \{a^i b^{2j} / i \geq 1\}

  1. Aaabbbbbb
  2. Abbabbba
  3. aabb
  4. aaaabbbbbb
Show me the answer

Answer: 4. aaaabbbbbb

Explanation:

  • The string aaaabbbbbbaaaabbbbbb fits the pattern aib2ja^i b^{2j} with i=4i = 4 and j=3j = 3.

5. Give a production grammar for the language L={x/x∈(a,b)∗L = \{x / x \in (a, b)^*, the number of aa’s in xx is multiple of 3}

  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\}
  2. {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\}
  3. {S→aaS,S→bbA,A→bB,B→ba}\{S \rightarrow aaS, S \rightarrow bbA, A \rightarrow bB, B \rightarrow ba\}
  4. None of the above
Show me the answer

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\}

Explanation:

  • The grammar ensures that the number of aa’s in the string is a multiple of 3.

6. Let L1={ab/i>j}L1 = \{a^b / i > j\} and L2={ab/i<j}L2 = \{a^b / i < j\}: the union of L1L1 and L2L2 is given by

  1. {ab/i,j≥1}\{a^b / i, j \geq 1\}
  2. ab/i>j≥1}a^b / i > j \geq 1\}
  3. {ab/i,j≥1}\{a^b / i, j \geq 1\}
  4. {ab/i,j≥1,i≠j}\{a^b / i, j \geq 1, i \neq j\}
Show me the answer

Answer: 4. {ab/i,j≥1,i≠j}\{a^b / i, j \geq 1, i \neq j\}

Explanation:

  • The union of L1L1 and L2L2 includes all strings where i≠ji \neq j.

7. Give a production grammar for the language

L={ab/I,j≥1,i≠j}L = \{a^b / I, j \geq 1, i \neq j\}

  1. {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\}
  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\}
  3. {S→A,A→aA,A→aB,B→ab}\{S \rightarrow A, A \rightarrow aA, A \rightarrow aB, B \rightarrow ab\}
  4. None of the above
Show me the answer

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\}

Explanation:

  • The grammar generates strings where the number of aa’s and bb’s are not equal.

8. The production grammar is {S→aSbb,S→abb}\{S \rightarrow aSbb, S \rightarrow abb\} is

  1. Type-3 grammar
  2. Type-1 grammar
  3. Type-3 grammar
  4. Type-0 grammar
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?

  1. A Turing machine cannot solve halting problem
  2. Set of recursively enumerable languages is closed under union
  3. A finite State Machine with 2 stacks
  4. 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?

  1. Recursive language are closed under union
  2. Recursive language are closed under union
  3. If a language and its complement are both regular, then the language must be recursive
  4. 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?

  1. Every recursive language is recursively enumerable
  2. A language is accepted by FA if and only if it is context free
  3. Recursive languages are closed under intersection
  4. 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?

  1. All language can be generated by CFG
  2. The number of symbols unnecessary to simulate a Turing Machine (TM) with mm symbols and nn states is mnmn
  3. Any regular language has an equivalent CFG
  4. 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

  1. Complementation
  2. Intersection
  3. Union
  4. None of the above
Show me the answer

Answer: 1. Complementation

Explanation:

  • Recursively enumerable languages are not closed under complementation.

14. Regular expression (x/y)(x/y) denotes the set

  1. {xy,xy}\{xy, xy\}
  2. {x,y}\{x,y\}
  3. {xx,xy,yx,yy}\{xx,xy,yx,yy\}
  4. {x,y,xy}\{x,y,xy\}
Show me the answer

Answer: 2. {x,y}\{x,y\}

Explanation:

  • The regular expression (x/y)(x/y) represents the set {x,y}\{x, y\}.

15. Regular expression x/yx/y denotes the set

  1. {x,y}\{x,y\}
  2. {xy}\{xy\}
  3. {x}\{x\}
  4. {y}\{y\}
Show me the answer

Answer: 1. {x,y}\{x,y\}

Explanation:

  • The regular expression x/yx/y represents the set {x,y}\{x, y\}.

16. The regular expressions denote a language comprising all possible strings of even length over the alphabet {0,1}\{0,1\}

  1. 1+0(1+0)∗1 + 0 (1 + 0)^*
  2. (1+0)(1 + 0)
  3. (0+1)(1+0)∗(0 + 1) (1 + 0)^*
  4. (00+011+10)∗(00 + 011 + 10)^*
Show me the answer

Answer: 4. (00+011+10)∗(00 + 011 + 10)^*

Explanation:

  • The regular expression (00+011+10)∗(00 + 011 + 10)^* generates all strings of even length over {0,1}\{0,1\}.

17. The regular expressions denote zero or more instances of an xx or yy is

  1. (x+y)(x + y)
  2. (x∗+y)(x^* + y)
  3. (x+y)∗(x + y)^*
  4. (xy)∗(xy)^*
Show me the answer

Answer: 3. (x+y)∗(x + y)^*

Explanation:

  • The regular expression (x+y)∗(x + y)^* denotes zero or more instances of xx or yy.

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:

  1. (0+1+2)∗(0 + 1 + 2)^*
  2. 0∗+1+20^* + 1 + 2
  3. 0∗1∗2∗0^* 1^* 2^*
  4. (0+1)∗2∗(0 + 1)^* 2^*
Show me the answer

Answer: 3. 0∗1∗2∗0^* 1^* 2^*

Explanation:

  • The regular expression 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.

19. The regular expression have all strings of 0’s and 1’s with no two consecutive 0’s, is

  1. (0+1)(0 + 1)
  2. (0+ϵ)(1+10)∗(0 + \epsilon) (1 + 10)^*
  3. (0+1)∗(0 + 1)^*
  4. (0+1)∗011(0 + 1)^* 011
Show me the answer

Answer: 2. (0+ϵ)(1+10)∗(0 + \epsilon) (1 + 10)^*

Explanation:

  • The regular expression (0+ϵ)(1+10)∗(0 + \epsilon) (1 + 10)^* ensures no two consecutive 0’s.

20. The regular expression with all strings of 0’s and 1’s with at least two consecutive 0’s is:

  1. 1+(10)∗1 + (10)^*
  2. (0+1)0(0 + 1)^0
  3. (0+1)0(0+1)∗(0 + 1)^0(0 + 1)^*
  4. 010^1
Show me the answer

Answer: 3. (0+1)0(0+1)∗(0 + 1)^0(0 + 1)^*

Explanation:

  • The regular expression (0+1)0(0+1)∗(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)∗bbabR = (ab + abb)^*bbab

  1. Ababbbbab
  2. Ababbabbbbab
  3. Abbbab
  4. Abababab
Show me the answer

Answer: 4. Abababab

Explanation:

  • The string abababababababab does not fit the pattern (ab+abb)∗bbab(ab + abb)^*bbab.

22. Which string can be generated by

S→aS/bA,A→d/cAS \rightarrow aS/bA, A \rightarrow d/cA

  1. Aabccd
  2. Abcca
  3. Adabcca
  4. Abababd
Show me the answer

Answer: 1. Aabccd

Explanation:

  • The string aabccdaabccd can be generated by the given grammar.

23. The regular sets are closed under

  1. Union
  2. Kleene’s closure
  3. Concentration
  4. All of the above
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?

  1. The regular sets are closed under intersection
  2. The class of regular sets is closed under substitution
  3. The class of regular sets is closed under homomorphisms
  4. 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

  1. Turing machine
  2. Context free languages
  3. Pushdown automata
  4. Regular language
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?

  1. A finite state machine can be considered to be a Turing Machine of finite tape length without rewinding capability and unidirectional tape movement
  2. Turing machine is more powerful than finite state machine because it has the capability to remember arbitrary long sequences of input symbol
  3. Palindromes can’t be recognized by any Finite State Machine (FSM) because an FSM can’t remember arbitrarily large amount of information
  4. 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.

27. Let LL be a Language recognizable by Finite automation. The Language REVERSE L′={ω/ωL' = \{ \omega / \omega is the reverse of vv where v∈L}v \in L\} is

  1. Regular language
  2. Context-free language
  3. Context-sensitive language
  4. Recursively enumerable language
Show me the answer

Answer: 1. Regular language

Explanation:

  • The reverse of a regular language is also regular.

28. The Grammar G=<{S},{0,1},P,S>G = <\{S\}, \{0, 1\}, P, S> Where pp is S→0SI,S→0S,S→SI,S→0S \rightarrow 0SI, S \rightarrow 0S, S \rightarrow SI, S \rightarrow 0 is

  1. Recursively enumerable language
  2. Regular expression
  3. Context-sensitive language
  4. Context free 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

  1. Regular expression
  2. DFSM (Deterministic Finite State Machine)
  3. NDFSM
  4. All of them
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

  1. Is always regular
  2. Both (A) and (C) above
  3. Is always context-free
  4. Need not be regular
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

  1. Deterministic pushdown Automata
  2. Non-deterministic pushdown automata
  3. Finite State Machine (FSM)
  4. 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?

  1. r′=rr' = r
  2. rS′=r+SrS' = r + S
  3. (r+S)′=r′+S′(r + S)' = r' + S'
  4. All of these
Show me the answer

Answer: 1. r′=rr' = r

Explanation:

  • The identity r′=rr' = r is true for regular expressions.

33. The Language L={0:1n2k3k where n,k>0}L = \{0:1n2k3k \text{ where } n, k > 0\}

  1. Context-sensitive language
  2. Context-free language
  3. Regular languages
  4. Recursively enumerable language
Show me the answer

Answer: 2. Context-free language

Explanation:

  • The language LL is context-free as it can be generated by a context-free grammar.

34. Consider the production grammar

S→XY/XSS \rightarrow XY/XS
X→a/aXX \rightarrow a/aX
Y→bY \rightarrow b
Which of the following regular expressions corresponding to the production grammar?

  1. (ab)(ab)
  2. a(ab)ba(ab)^{b}
  3. aabba^a b^b
  4. aaba^a b
Show me the answer

Answer: 4. aaba^a b

Explanation:

  • The grammar generates strings of the form aaba^a b.

35. Which of the following sentences is generated by production grammar?

S→aSbXS \rightarrow aSbX
X→dccXX \rightarrow dccX

  1. Abblod
  2. aabccd
  3. aabd
  4. ababccd
Show me the answer

Answer: 2. aabccd

Explanation:

  • The string aabccdaabccd can be generated by the given grammar.

36. Consider a NDFA shown in figure below. The Automation accepts

  1. All words that contain the substring ab and end with a
  2. All words that contain the substring ba and end with a
  3. All words that end with a, but not the null string ϵ\epsilon
  4. All words that end with a, and also the null string
Show me the answer

Answer: 3. All words that end with a, but not the null string ϵ\epsilon

Explanation:

  • The NDFA accepts words ending with aa but not the null string.

37. Which of the following is accepted by deterministic pushdown machine but not accepted by non-deterministic pushdown machine (NDPDM)?

  1. Strings end with a particular alphabet
  2. All strings in which a given symbol is present at least twice
  3. Even palindrome
  4. None of these
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

X→Xx/YyX \rightarrow Xx/Yy
X→Yy/ZωX \rightarrow Yy/Z\omega
Y→y/YwY \rightarrow y/Yw
Z→yZ \rightarrow y
Which of the regular expressions describe the same set of strings as the grammar?

  1. xωy+xωyx+yωxx\omega y + x\omega yx + y\omega x
  2. xωy+xωxy+yωxx\omega y + x\omega xy + y\omega x
  3. xωy+xωxyx+yωx+yωxx\omega y + x\omega xyx + y\omega x + y\omega x
  4. xωxy+xωωy+yωxx\omega xy + x\omega \omega y + y\omega x
Show me the answer

Answer: 1. xωy+xωyx+yωxx\omega y + x\omega yx + y\omega x

Explanation:

  • The regular expression xωy+xωyx+yωxx\omega y + x\omega yx + y\omega x matches the strings generated by the grammar.

39. Which of the following instance of the post correspondence problem have a viable sequence?

  1. {(x,xx),(xx,xyx),(xyx,yxx),(yyxx,xyyx)}\{(x, xx), (xx, xyx), (xyx, yxx), (yyxx, xyyx)\}
  2. {(yx,yxy),(xyy,yy),(yyxy,yyy)}\{(yx, yxy), (xyy, yy), (yyxy, yyy)\}
  3. {(yx,yxx),(xy,yyy),(yy,y)}\{(yx, yxx), (xy, yyy), (yy, y)\}
  4. None of the above
Show me the answer

Answer: 3. {(yx,yxx),(xy,yyy),(yy,y)}\{(yx, yxx), (xy, yyy), (yy, y)\}

Explanation:

  • The instance {(yx,yxx),(xy,yyy),(yy,y)}\{(yx, yxx), (xy, yyy), (yy, y)\} has a viable sequence.

40. Which of the following statement(s) is (are) correct?

  1. Recursively languages are closed under complementation
  2. If a language and its complement are both recursively enumerable then language is recursive
  3. Set of recursively enumerable language is closed under union
  4. All of these
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

  1. (a+b)∗b(a + b)^* b
  2. (a+b)∗b(a + b)^* b
  3. a∗ba^* b
  4. a∗ba^* b
Show me the answer

Answer: 2. (a+b)∗b(a + b)^* b

Explanation:

  • The FA accepts all strings ending with bb.

42. Which of the following statement is wrong

  1. Any regular language has an equivalent context-free grammar
  2. Some non-regular languages can’t be generated by any context-free grammar
  3. The intersection of context free languages and a regular language is always context-free
  4. 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

S→SSS \rightarrow SS
S→0S1S \rightarrow 0S1
S→1S0S \rightarrow 1S0
S→ϵS \rightarrow \epsilon
The grammar will generate

  1. Regular language
  2. Context-free language
  3. Context sensitive language
  4. 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

  1. Regular expression
  2. Non-context free grammars
  3. Context-free grammar
  4. None of these
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

  1. Ambiguous
  2. Regular
  3. Unambiguous
  4. None of these
Show me the answer

Answer: 1. Ambiguous

Explanation:

  • A grammar that produces more than one parse tree for the same sentence is ambiguous.

46. Which of the regular expression denotes a language containing all possible strings over the alphabet {a,b}\{a, b\}?

  1. a∗b∗a^* b^*
  2. (a,b)∗(a, b)^*
  3. (ab)∗(ab)^*
  4. (a+b)∗(a + b)^*
Show me the answer

Answer: 4. (a+b)∗(a + b)^*

Explanation:

  • The regular expression (a+b)∗(a + b)^* denotes all possible strings over {a,b}\{a, b\}.

47. Palindromes can’t be recognized by any Finite State Machine because

  1. An FSM can’t remember arbitrarily large amount of information
  2. An FSM can’t fix the mid-point
  3. FSM can’t find whether the second half of the string matches the first half
  4. All of these
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.

48. A language LL is accepted by FA if and only if it is

  1. Context-free
  2. Recursive
  3. Context sensitive
  4. Right-linear
Show me the answer

Answer: 4. Right-linear

Explanation:

  • A language accepted by a finite automaton (FA) is right-linear.

49. A language is denoted by a regular expression L={x∗(x/y)x}L = \{x^*(x/y)x\}. Which of the following is not a legal string within LL?

  1. Yx
  2. yxx
  3. x
  4. xy xyx
Show me the answer

Answer: 4. xy xyx

Explanation:

  • The string xyxyxxy xyx does not fit the pattern x∗(x/y)xx^*(x/y)x.

50. Can a DFA simulate NFA?

  1. No
  2. Sometimes
  3. Yes
  4. Depends on NFA
Show me the answer

Answer: 3. Yes

Explanation:

  • A Deterministic Finite Automaton (DFA) can simulate a Non-deterministic Finite Automaton (NFA).
Last updated on
set-6set-2