Computer Science Engineering (CSE)  >  Theory of Computation  >  Test: Context Free Grammar Derivations & Definitions Download as PDF

Test: Context Free Grammar Derivations & Definitions


Test Description

10 Questions MCQ Test Theory of Computation | Test: Context Free Grammar Derivations & Definitions

Test: Context Free Grammar Derivations & Definitions for Computer Science Engineering (CSE) 2023 is part of Theory of Computation preparation. The Test: Context Free Grammar Derivations & Definitions questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Context Free Grammar Derivations & Definitions MCQs are made for Computer Science Engineering (CSE) 2023 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Context Free Grammar Derivations & Definitions below.
Solutions of Test: Context Free Grammar Derivations & Definitions questions in English are available as part of our Theory of Computation for Computer Science Engineering (CSE) & Test: Context Free Grammar Derivations & Definitions solutions in Hindi for Theory of Computation course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Context Free Grammar Derivations & Definitions | 10 questions in 20 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Theory of Computation for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
1 Crore+ students have signed up on EduRev. Have you?
Test: Context Free Grammar Derivations & Definitions - Question 1

 The entity which generate Language is termed as:

Detailed Solution for Test: Context Free Grammar Derivations & Definitions - Question 1

The entity which accepts a language is termed as Automata while the one which generates it is called Grammar. Tokens are the smallest individual unit of a program.

Test: Context Free Grammar Derivations & Definitions - Question 2

 Production Rule: aAb->agb belongs to which of the following category?

Detailed Solution for Test: Context Free Grammar Derivations & Definitions - Question 2

Context Sensitive Language or Type 1 or Linearly Bounded Non deterministic Language has the production rule where the production is context dependent i.e. aAb->agb.

Test: Context Free Grammar Derivations & Definitions - Question 3

Which of the following statement is false?

Detailed Solution for Test: Context Free Grammar Derivations & Definitions - Question 3

Every regular language can be produced by context free grammar and context free language can be produced by context sensitive grammar and so on.

Test: Context Free Grammar Derivations & Definitions - Question 4

The Grammar can be defined as: G=(V, ∑, p, S)In the given definition, what does S represents?

Detailed Solution for Test: Context Free Grammar Derivations & Definitions - Question 4

G=(V, ∑, p, S), here V=Finite set of variables, ∑= set of terminals, p= finite productions, S= Starting Variable.

Test: Context Free Grammar Derivations & Definitions - Question 5

Which among the following cannot be accepted by a regular grammar?

Detailed Solution for Test: Context Free Grammar Derivations & Definitions - Question 5

There exists no finite automata to accept the given language i.e. 0n1n. For other options, it is possible to make a dfa or nfa representing the language set.

Test: Context Free Grammar Derivations & Definitions - Question 6

 Which of the expression is appropriate? For production p: a -> b where a ∈ V and b ∈  _______

Detailed Solution for Test: Context Free Grammar Derivations & Definitions - Question 6

According to the definition, the starting variable can produce another variable or any terminal or a variable which leads to terminal.

Test: Context Free Grammar Derivations & Definitions - Question 7

 For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?

Detailed Solution for Test: Context Free Grammar Derivations & Definitions - Question 7

L={e, 01, 0011, 000111, ……0n1n }. As epsilon is a part of the set, thus all the options are correct implying none of them to be wrong.

Test: Context Free Grammar Derivations & Definitions - Question 8

The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is

Detailed Solution for Test: Context Free Grammar Derivations & Definitions - Question 8

The grammar which produces a palindrome set can be written as:
S-> aSa | bSb | e | a | b
L={e, a, b, aba, abbbaabbba…..}

Test: Context Free Grammar Derivations & Definitions - Question 9

Which of the following statement is correct?

Detailed Solution for Test: Context Free Grammar Derivations & Definitions - Question 9

 Regular grammar is a subset of context free grammar and thus all regular grammars are context free.

Test: Context Free Grammar Derivations & Definitions - Question 10

 Are ambiguous grammar context free?

Detailed Solution for Test: Context Free Grammar Derivations & Definitions - Question 10

 A context free grammar G is ambiguous if there is atleast one string in L(G) which has two or more distinct leftmost derivations.

18 videos|56 docs|41 tests
Use Code STAYHOME200 and get INR 200 additional OFF
Use Coupon Code
Information about Test: Context Free Grammar Derivations & Definitions Page
In this test you can find the Exam questions for Test: Context Free Grammar Derivations & Definitions solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Context Free Grammar Derivations & Definitions, EduRev gives you an ample number of Online tests for practice