Regular and context free languages Questions

MCQ bookmark_border

1.

The entity which generate Language is termed as:

A

Automata

B

Tokens

C

Grammer

D

Data

Correct Answer: C

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.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

2.

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

A

Regular Language

B

Context free Language

C

Context Sensitive Language

D

Recursively Ennumerable Language

Correct Answer: C

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.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

3.

Which of the following statement is false?

A

Context free language is the subset of context sensitive language

B

Regular language is the subset of context sensitive language

C

Recursively ennumerable language is the super set of regular language

D

Context sensitive language is a subset of context free language

Correct Answer: D

Every regular language can be produced by context free grammar and context free language can be produced by context sensitive grammar and so on. Find the context sensitive language from the given diagram

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

4.

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

A

Accepting State

B

Starting Variable

C

Sensitive Grammar

D

None of these

Correct Answer: B

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

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

5.

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

A

L is a set of numbers divisible by 2

B

L is a set of binary complement

C

L is a set of string with odd number of 0

D

L is a set of 0ⁿ1ⁿ

Correct Answer: D

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.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

6.

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

A

V

B

S

C

(V+?)*

D

V+ ?

Correct Answer: C

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

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

7.

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

A

Non regular language

B

0ⁿ1ⁿ | n>=0

C

0ⁿ1ⁿ | n>=1

D

None of the mentioned

Correct Answer: D

L={e, 01, 0011, 000111,

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

8.

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

A

3

B

7

C

5

D

6

Correct Answer: C

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

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

9.

Which of the following statement is correct?

A

All Regular grammar are context free but not vice versa

B

All context free grammar are regular grammar but not vice versa

C

Regular grammar and context free grammar are the same entity

D

None of the mentioned

Correct Answer: A

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

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

10.

Are ambiguous grammar context free?

A

Yes

B

No

C

Explanation :

D

class="v-slide-group__next v-slide-group__next--disabled">

Explanation :

Correct Answer: A