Site icon T4Tutorials.com

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


GRAMMAR AUTOMATA MACHINE TYPE
Regular Finite State Automaton Type 3: Regular
Context Free Pushdown Automaton Type 2: Context Free
Context Sensitive Linear Bounded Automaton Type 1: CS
Recursively Enumerable Turing Machine Type 0: Unrestricted

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

Ambiguous Grammar

 

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

Exit mobile version