MCQs on Context free Grammar and Context Sensitive Languages

MCQs on Context free Grammar and Context Sensitive Languages in Theory of Automata

The entity which generate Language is termed as:
(a) Automata
(b) Tokens
(c) Strings
(d) Grammar

---

The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is
(a) 5
(b) 7
(c) 3
(d) 8

---

Which of the following statement is correct?
(a) All context free grammar are regular grammar but not vice versa
(b) All Regular grammar are context free but not vice versa

(c) Regular grammar and context free grammar are the same entity
(d) None of the mentioned

---

Context sensitive grammar (CSL) is also called?
(a) Length increasing grammar

(b) Non contracting Grammar

(c) Type 1 Grammar
(d) All of these

---

---

Which of the following is  Type 3 language or Type 3 grammar?
(a) Regular grammar/ Regular language

(b) Context Free Grammar / Context Free

language

(c) Context Sensitive Grammar / Context   Sensitive  language
(d) Recursively Enumerable

---

Which of the following is  Type 2 language or Type 2 grammar?
(a) Regular grammar/ Regular language

(b) Context Free Grammar / Context Free

language

(c) Context Sensitive Grammar / Context Sensitive  language
(d) Recursively Enumerable

---

Which of the following is  Type 1 language or Type 1 grammar?
(a) Regular grammar/ Regular language

(b) Context Free Grammar / Context Free

language

(c) Context Sensitive Grammar / Context Sensitive  language
(d) Recursively Enumerable

---

Which of the following is  Type 0 language?
(a) Regular grammar/ Regular language

(b) Context Free Grammar / Context Free

language

(c) Context Sensitive Grammar / Context Sensitive  language
(d) Recursively Enumerable

---

Which of the following Machine is specific for Regular grammar?
(a) Finite state automata

(b) Push down automata

(c) Linear bounded automata

(d) Turing Machine with deterministic logic, unbounded infinite length of tape.

---

Which of the following Machine is specific for Context free grammar?
(a) Finite state automata

(b) Push down automata

(c) Linear bounded automata

(d) Turing Machine

---

Which of the following Machine is specific for Context sensitive grammar?
(a) Finite state automata

(b) Push down automata

(c) Linear bounded automata

(d) Turing Machine

Explanation: Linear Bounded Automaton is a

1.Turing Machine with Multi-track

2.Turing Machine with a bounded finite length of the tape.

3.Turing Machine with Non-deterministic logic

---

Which of the following Machine is specific for Recursively enumerable languages?
(a) Finite state automata

(b) Push down automata

(c) Linear bounded automata

(d) Turing Machine

---

A context free language is called ambiguous if there exists a  string  that can have?
(a) only one parse tree

  (b) more than one parse tree

(c) no parse tree

(d)  Partial parse tree

Explanation:

For example, we
have a CFG.

S →XY | mmY

X →m | Xm

Y →n

 

The context free grammar

X → XX | aXb | bXa | ɛ

generates __?
(a) Number of a’s followed by any number of b’s

(b) Unequal number of a’s and b’s

(c) Equal number of a’s and b’s

(d) None of these

---

Production Rule:

aYb->agb

belongs to which of the following languages?
(a) Recursively Enumerable Language

(b) Context free Language
(c) Context Sensitive Language
(d) Regular Language

---

Which of the following language cannot be accepted by a regular expression?

(a) Language of a set of numbers divisible by 4

(b) Language of a set of binary complement

(c) Language of a set of 0n1n

(d) Language of a set of string with odd number of 0

---

The minimum number of productions required to produce a language consisting of palindromes as a  strings defined over ∑={0,1} is
(a) 4
(b) 5
(c) 6
(d) 7

---

Which of the following statement is true about regular grammar?
(a) Regular grammar and context free
(b) All context free grammar are regular grammar but not vice versa
(c) All Regular grammar are context free but not vice versa grammar are the same entity
(d) All of these

---

Are ambiguous grammar context free?
(a) Yes
(b) No

 

• Theory of Automata MCQs
• Finite Automata MCQs
  • Deterministic Finite Automata (DFA) MCQs
  • Non-deterministic Finite Automata (NFA) MCQs
  • Equivalence of DFA and NFA MCQs
  • Minimization of DFA MCQs
• Regular Languages
  • Regular Expression MCQs
  • Properties of regular languages MCQs
  • Closure properties MCQs
  • Pumping Lemma for regular languages MCQs
• Context-Free Grammars (CFG)
  • CFG MCQs
  • Parse trees and derivations MCQs
  • Ambiguity in grammars MCQs
• Pushdown Automata (PDA) MCQs
  • Deterministic PDA vs Non-deterministic PDA MCQs
  • Relationship between PDA and context-free languages MCQs
• Context-Free Languages MCQs
  • Properties of context-free languages MCQs
  • Closure properties MCQs
  • Pumping Lemma for context-free languages MCQs
• Turing Machines MCQs
  • Turing machine as a language recognizer and transducer MCQs
• Decidability and Undecidability MCQs
  • Decidable languages and problems MCQs
  • Undecidable languages and problems MCQs
  • Rice’s theorem MCQs
  • Reduction techniques MCQs
• Computational Complexity MCQs
  • Time complexity classes (P, NP, NP-complete, NP-hard) MCQs
  • Space complexity classes (PSPACE, L, NL) MCQs
  • Polynomial time reductions MCQs
• Advanced Topics in Automata Theory
  • Linear-bounded automata MCQs
  • Context-sensitive grammars and languages MCQs
  • Chomsky hierarchy MCQs
  • Introduction to quantum automata MCQs
• Applications of Automata Theory MCQs