computer-nec-license
  • NEC-Computer
  • 1. Concept of Basic Electrical and Electronics Engineering
    • 1.1 Basic Concepts
    • 1.2 Network Theorems
    • 1.3 Alternating Current Fundamentals
    • 1.4 Semiconductor Device
    • 1.5 Signal Generator
    • 1.6 Amplifiers
    • MCQs
      • MCQs On Basic Electrical
        • set-1
        • set-2
      • MCQs On Basic Electronics
        • set-1
        • set-2
  • 2. Digital Logic and Microprocessor
    • 2.1 Digital Logic
    • 2.2 Combinational & Arithmetic Circuit
    • 2.3 Sequential Logic Circuits
    • 2.4 Microprocessor
    • 2.5 Microprocessor System
    • 2.6 Interrupt Operations
    • MCQs
      • MCQs On Digital Logic
        • set-1
        • set-2
        • set-3
        • set-4
        • set-5
        • set-6
        • set-7
        • set-8
        • set-9
        • set-10
        • set-11
        • set-12
      • MCQs On Microprocessor
        • set-1
        • set-2
        • set-3
        • set-4
        • set-5
        • set-6
        • set-7
        • set-8
        • set-9
  • 3. Programming Language and Its Applications
    • 3.1 Introduction to C Programming
    • 3.2 Pointers, Structures, and Data Files
    • 3.3 C++ Language Constructs with Objects and Classes
    • 3.4 Features of Object-Oriented Programming
    • 3.5 Pure Virtual Functions and File Handling
    • 3.6 Generic Programming and Exception Handling
    • MCQs
      • set-1
      • set-2
      • set-3
      • set-4
      • set-5
  • 4. Computer Organization and Embedded System
    • 4.1 Control and CPU
    • 4.2 Computer Arithmetic and Memory System
    • 4.3 I/O Organization and Multiprocessor
    • 4.4 Embedded System Design
    • 4.5 Real-Time Operating and Control Systems
    • 4.6 Hardware Description Language (VHDL) and IC Technology
    • MCQs
      • set-1
      • set-2
      • set-3
      • set-4
      • set-5
      • set-6
      • set-7
      • set-8
      • set-9
      • set-10
      • set-11
  • 5. Concept of Computer Network and Network Security System
    • 5.1 Introduction to Computer Networks
    • 5.2 Data Link Layer
    • 5.3 Network Layer
    • 5.4 Transport Layer
    • 5.5 Application Layer
    • 5.6 Network Security
    • MCQs
      • Basic Networking
        • set-1
        • set-2
      • Advanced Networking
        • set-1
        • set-2
        • set-3
        • set-4
        • set-5
        • set-6
  • 6. Theory of Computation and Computer Graphics
    • 6.1 Introduction to Finite Automata
    • 6.2 Introduction to Context-Free Languages (CFL)
    • 6.3 Turing Machines (TM)
    • 6.4 Introduction to Computer Graphics
    • 6.5 Two-Dimensional Transformation
    • 6.6 Three-Dimensional Transformation
    • MCQs
      • MCQs on Theory of Computation
        • set-1
        • set-2
        • set-3
      • MCQs On Computer Graphics
        • set-1
        • set-2
        • set-3
        • set-4
        • set-5
        • set-6
  • 7. Data Structures and Algorithm, Database System and Operating System
    • 7.1 Introduction to Data Structures, Lists, Linked Lists, and Trees
    • 7.2 Sorting, Searching, Hashing and Graphs
    • 7.3 Introduction to Data Models, Normalization, and SQL
    • 7.4 Transaction Processing, Concurrency Control, and Crash Recovery
    • 7.5 Introduction to Operating System and Process Management
    • 7.6 Memory Management, File Systems, and System Administration
    • MCQs
      • MCQs ON DSA
        • set-1
        • set-2
        • set-3
        • set-4
        • set-5
        • set-6
      • MCQs On DBMS
        • set-1
        • set-2
      • MCQs On Operating System
        • set-1
        • set-2
        • set-3
        • set-4
        • set-5
        • set-6
        • set-7
        • set-8
        • set-9
        • set-10
        • set-11
        • set-12
  • 8. Software Engineering and Object-Oriented Analysis & Design
    • 8.1 Software Process and Requirements
    • 8.2 Software Design
    • 8.3 Software Testing, Cost Estimation, Quality Management, and Configuration Management
    • 8.4 Object-Oriented Fundamentals and Analysis
    • 8.5 Object-Oriented Design
    • 8.6 Object-Oriented Design Implementation
    • MCQs
      • set-1
      • set-2
      • set-3
      • set-4
      • set-5
      • set-6
      • set-7
      • set-8
      • set-9
  • 9. Artificial Intelligence and Neural Networks
    • 9.1 Introduction to AI and Intelligent Agents
    • 9.2 Problem Solving and Searching Techniques
    • 9.3 Knowledge Representation
    • 9.4 Expert System and Natural Language Processing
    • 9.5 Machine Learning
    • 9.6 Neural Networks
    • MCQs
      • set-1
      • set-2
      • set-3
      • set-4
      • set-5
      • set-6
      • set-7
      • set-8
      • set-9
  • 10. Project Planning, Design and Implementation
    • 10.1 Engineering Drawings and Its Concepts
    • 10.2 Engineering Economics
    • 10.3 Project Planning and Scheduling
    • 10.4 Project Management
    • 10.5 Engineering Professional Practice
    • 10.6 Engineering Regulatory Body
    • MCQs
      • MCQs On Engineering Drawing
        • set-1
        • set-2
      • MCQs On Engineering Economics
      • MCQs On Project Planning & Scheduling
      • MCQs On Project Mangement
      • MCQs On Engineering Professional Practice
      • MCQs On Engineering Regulatory Body
  • Questions Sets
    • Set 1 (Chaitra, 2080)
      • Short Questions (60*1=60 Marks)
      • Long Questions (20*2=40 Marks)
    • Set 2 (Aasadh, 2081)
      • Short Questions (60*1=60 Marks)
      • Long Questions (20*2=40 Marks)
    • Set 3 (Asojh, 2080)
      • Short Questions (60*1=60 Marks)
      • Long Questions (20*2=40 Marks)
    • Model Set - Computer Engineering By NEC
      • Short Questions (60*1=60 Marks)
      • Long Questions (20*2=40 Marks)
    • Model Set - Software Engineering By NEC
      • Short Questions (60*1=60 Marks)
      • Long Questions (20*2=40 Marks)
  • Tips & Tricks
Powered by GitBook
On this page
  1. 6. Theory of Computation and Computer Graphics
  2. MCQs
  3. MCQs on Theory of Computation

set-1

1. Let R1R_1R1​ and R2R_2R2​ be regular sets defined over alphabet ∑\sum∑ then

  1. R1∪R2R_1 \cup R_2R1​∪R2​ is regular

  2. ∑∩R2\sum \cap R_2∑∩R2​is not regular

  3. R1∩R2R_1 \cap R_2R1​∩R2​ is not regular

  4. R2R_2R2​ is not regular

Show me the answer

Answer: 1. R1∪R2R_1 \cup R_2R1​∪R2​ is regular

Explanation:

  • The union of two regular sets is also regular.

2. Consider the production of the grammar

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

Describe the language specified by the production grammar

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

  2. L={abab,abaa,aaab,baaa}L = \{abab, abaa, aaab, baaa\}L={abab,abaa,aaab,baaa}

  3. L={aaab,baba,bbaa,bbbb}L = \{aaab, baba, bbaa, bbbb\}L={aaab,baba,bbaa,bbbb}

  4. L={aaaa,ababa,bbaa,aaab}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\}L={aaaa,aabb,bbaa,bbbb}

Explanation:

  • The grammar generates strings of even length with aaa and bbb.

3. Give a production grammar that specifies the language

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

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

  2. {S→aA,S→b,A→b}\{S \rightarrow aA, S \rightarrow b, A \rightarrow b\}{S→aA,S→b,A→b}

  3. {S→aSb,S→b}\{S \rightarrow aSb, S \rightarrow b\}{S→aSb,S→b}

  4. None of the above

Show me the answer

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

Explanation:

  • The grammar generates strings with aib2ja^i b^{2j}aib2j where i≥1i \geq 1i≥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\}L={aib2j/i≥1}

  1. Aaabbbbbb

  2. Abbabbba

  3. aabb

  4. aaaabbbbbb

Show me the answer

Answer: 4. aaaabbbbbb

Explanation:

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

5. Give a production grammar for the language L={x/x∈(a,b)∗L = \{x / x \in (a, b)^*L={x/x∈(a,b)∗, the number of aaa’s in xxx 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\}{S→bS,S→b,S→aA,S→bA,A→aB,B→bB,B→aS,S→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\}{S→aS,S→bA,A→bB,B→bBa,B→bB}

  3. {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}

  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\}{S→bS,S→b,S→aA,S→bA,A→aB,B→bB,B→aS,S→a}

Explanation:

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

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

  1. {ab/i,j≥1}\{a^b / i, j \geq 1\}{ab/i,j≥1}

  2. ab/i>j≥1}a^b / i > j \geq 1\}ab/i>j≥1}

  3. {ab/i,j≥1}\{a^b / i, j \geq 1\}{ab/i,j≥1}

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

Show me the answer

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

Explanation:

  • The union of L1L1L1 and L2L2L2 includes all strings where i≠ji \neq ji=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\}L={ab/I,j≥1,i=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\}{S→aS,S→aB,B→ab,A→aaB,B→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\}{S→A,S→C,A→aA,A→aB,B→aBb,B→ab,C→Cb,E→Bb}

  3. {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}

  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\}{S→A,S→C,A→aA,A→aB,B→aBb,B→ab,C→Cb,E→Bb}

Explanation:

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

8. The production grammar is {S→aSbb,S→abb}\{S \rightarrow aSbb, S \rightarrow abb\}{S→aSbb,S→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 mmm symbols and nnn states is mnmnmn

  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)(x/y) denotes the set

  1. {xy,xy}\{xy, xy\}{xy,xy}

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

  3. {xx,xy,yx,yy}\{xx,xy,yx,yy\}{xx,xy,yx,yy}

  4. {x,y,xy}\{x,y,xy\}{x,y,xy}

Show me the answer

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

Explanation:

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

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

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

  2. {xy}\{xy\}{xy}

  3. {x}\{x\}{x}

  4. {y}\{y\}{y}

Show me the answer

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

Explanation:

  • The regular expression x/yx/yx/y represents the set {x,y}\{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\}{0,1}

  1. 1+0(1+0)∗1 + 0 (1 + 0)^*1+0(1+0)∗

  2. (1+0)(1 + 0)(1+0)

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

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

Show me the answer

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

Explanation:

  • 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}.

17. The regular expressions denote zero or more instances of an xxx or yyy is

  1. (x+y)(x + y)(x+y)

  2. (x∗+y)(x^* + y)(x∗+y)

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

  4. (xy)∗(xy)^*(xy)∗

Show me the answer

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

Explanation:

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

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)^*(0+1+2)∗

  2. 0∗+1+20^* + 1 + 20∗+1+2

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

  4. (0+1)∗2∗(0 + 1)^* 2^*(0+1)∗2∗

Show me the answer

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

Explanation:

  • 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.

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)(0+1)

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

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

  4. (0+1)∗011(0 + 1)^* 011(0+1)∗011

Show me the answer

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

Explanation:

  • The regular expression (0+ϵ)(1+10)∗(0 + \epsilon) (1 + 10)^*(0+ϵ)(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)^*1+(10)∗

  2. (0+1)0(0 + 1)^0(0+1)0

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

  4. 010^101

Show me the answer

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

Explanation:

  • 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.

21. Which of the following is NOT the set of regular expression R=(ab+abb)∗bbabR = (ab + abb)^*bbabR=(ab+abb)∗bbab

  1. Ababbbbab

  2. Ababbabbbbab

  3. Abbbab

  4. Abababab

Show me the answer

Answer: 4. Abababab

Explanation:

  • The string abababababababababababab does not fit the pattern (ab+abb)∗bbab(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/cAS→aS/bA,A→d/cA

  1. Aabccd

  2. Abcca

  3. Adabcca

  4. Abababd

Show me the answer

Answer: 1. Aabccd

Explanation:

  • The string aabccdaabccdaabccd 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 LLL be a Language recognizable by Finite automation. The Language REVERSE L′={ω/ωL' = \{ \omega / \omegaL′={ω/ω is the reverse of vvv where v∈L}v \in L\}v∈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>G=<{S},{0,1},P,S> Where ppp is S→0SI,S→0S,S→SI,S→0S \rightarrow 0SI, S \rightarrow 0S, S \rightarrow SI, S \rightarrow 0S→0SI,S→0S,S→SI,S→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' = rr′=r

  2. rS′=r+SrS' = r + SrS′=r+S

  3. (r+S)′=r′+S′(r + S)' = r' + S'(r+S)′=r′+S′

  4. All of these

Show me the answer

Answer: 1. r′=rr' = rr′=r

Explanation:

  • The identity r′=rr' = 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\}L={0:1n2k3k 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 LLL is context-free as it can be generated by a context-free grammar.

34. Consider the production 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?

  1. (ab)(ab)(ab)

  2. a(ab)ba(ab)^{b}a(ab)b

  3. aabba^a b^baabb

  4. aaba^a baab

Show me the answer

Answer: 4. aaba^a baab

Explanation:

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

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

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

  1. Abblod

  2. aabccd

  3. aabd

  4. ababccd

Show me the answer

Answer: 2. aabccd

Explanation:

  • The string aabccdaabccdaabccd 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 aaa 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/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?

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

  2. xωy+xωxy+yωxx\omega y + x\omega xy + y\omega xxωy+xωxy+yωx

  3. 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

  4. xωxy+xωωy+yωxx\omega xy + x\omega \omega y + y\omega xxωxy+xωωy+yωx

Show me the answer

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

Explanation:

  • 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.

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)\}{(x,xx),(xx,xyx),(xyx,yxx),(yyxx,xyyx)}

  2. {(yx,yxy),(xyy,yy),(yyxy,yyy)}\{(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)\}{(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)\}{(yx,yxx),(xy,yyy),(yy,y)}

Explanation:

  • The instance {(yx,yxx),(xy,yyy),(yy,y)}\{(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(a+b)∗b

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

  3. a∗ba^* ba∗b

  4. a∗ba^* ba∗b

Show me the answer

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

Explanation:

  • The FA accepts all strings ending with bbb.

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 SSS→SS S→0S1S \rightarrow 0S1S→0S1 S→1S0S \rightarrow 1S0S→1S0 S→ϵS \rightarrow \epsilonS→ϵ 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\}{a,b}?

  1. a∗b∗a^* b^*a∗b∗

  2. (a,b)∗(a, b)^*(a,b)∗

  3. (ab)∗(ab)^*(ab)∗

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

Show me the answer

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

Explanation:

  • The regular expression (a+b)∗(a + b)^*(a+b)∗ denotes all possible strings over {a,b}\{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 LLL 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\}L={x∗(x/y)x}. Which of the following is not a legal string within LLL?

  1. Yx

  2. yxx

  3. x

  4. xy xyx

Show me the answer

Answer: 4. xy xyx

Explanation:

  • The string xyxyxxy xyxxyxyx does not fit the pattern x∗(x/y)xx^*(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).

PreviousMCQs on Theory of ComputationNextset-2

Last updated 3 months ago