This set of Automata Theory Problems focuses on “The Language of a Grammar, Inferences and Ambiguity”.

1. Which of the following is not a notion of Context free grammars?

a) Recursive Inference

b) Derivations

c) Sentential forms

d) All of the mentioned

View Answer

Explanation: The following are the notions to express Context free grammars:

a) Recursive Inferences

b) Derivations

c) Sentential form

d) Parse trees

2. State true or false:

Statement: The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.

a) true

b) false

View Answer

Explanation: We apply the productions of CFG to infer that certain strings are in the language of a certain variable.

3. Which of the following is/are the suitable approaches for inferencing?

a) Recursive Inference

b) Derivations

c) Both Recursive Inference and Derivations

d) None of the mentioned

View Answer

Explanation: Two inference approaches:

1. Recursive inference, using productions from body to head

2. Derivations, using productions from head to body

4. If w belongs to L(G), for some CFG, then w has a parse tree, which defines the syntactic structure of w. w could be:

a) program

b) SQL-query

c) XML document

d) All of the mentioned

View Answer

Explanation: Parse trees are an alternative representation to derivations and recursive inferences. There can be several parse trees for the same string.

5. Is the following statement correct?

Statement: Recursive inference and derivation are equivalent.

a) Yes

b) No

View Answer

Explanation: Yes, they are equivalent. Both the terminologies represent the two approaches of recursive inferencing.

6. A->aA| a| b

The number of steps to form aab:

a) 2

b) 3

c) 4

d) 5

View Answer

Explanation: A->aA=>aaA=>aab

7. An expression is mentioned as follows. Figure out number of incorrect notations or symbols, such that a change in those could make the expression correct.

L(G)={w in T*|S→*w}

a) 0 Errors

b) 1 Error

c) 2 Error

d) Invalid Expression

View Answer

Explanation: For the given expression, L(G)={w in T*|S→*w}, If G(V, T, P, S) is a CFG, the language of G, denoted by L(G), is the set of terminal strings that have derivations from the start symbol.

8. The language accepted by Push down Automaton:

a) Recursive Language

b) Context free language

c) Linearly Bounded language

d) All of the mentioned

View Answer

Explanation: Push down automata accepts context free language.

9. Which among the following is the correct option for the given grammar?

G->X111|G1,X->X0|00

a) {0^{a}1^{b}|a=2,b=3}

b) {0^{a}1^{b}|a=1,b=5}

c) {0^{a}1^{b}|a=b}

d) More than one of the mentioned is correct

View Answer

Explanation: Using the recursive approach, we can conclude that option a is the correct answer, and its not possible for a grammar to have more than one language.

10. Which of the following the given language belongs to?

L={a^{m}b^{m}c^{m}| m>=1}

a) Context free language

b) Regular language

c) Both (a) and (b)

d) None of the mentioned

View Answer

Explanation: The given language is neither accepted by a finite automata or a push down automata. Thus, it is neither a context free language nor a regular language.

11. Choose the correct option:

Statement: There exists two inference approaches:

a) Recursive Inference

b) Derivation

a) true

b) partially true

c) false

d) none of the mentioned

View Answer

Explanation: We apply the productions of a CFG to infer that certain strings are in a language of certain variable.

12. Choose the correct option:

Statement 1: Recursive Inference, using productions from head to body.

Statement 2: Derivations, using productions from body to head.

a) Statement 1 is true and Statement 2 is true

b) Statement 1 and Statement 2, both are false

c) Statement 1 is true and Statement 2 is false

d) Statement 2 is true and Statement 1 is true

View Answer

Explanation: Both the statements are false. Recursive Inference, using productions from body to head. Derivations, using productions from head to body.

13. Which of the following statements are correct for a concept called inherent ambiguity in CFL?

a) Every CFG for L is ambiguous

b) Every CFG for L is unambiguous

c) Every CFG is also regular

d) None of the mentioned

View Answer

Explanation: A CFL L is said to be inherently ambiguous if every CFG for L is ambiguous.

14. Which of the theorem defines the existence of Parikhs theorem?

a) Parikh’s theorem

b) Jacobi theorem

c) AF+BG theorem

d) None of the mentioned

View Answer

Explanation: Rohit Parikh in 1961 proved in his MIT research paper that some context free language can only have ambiguous grammars.

**Sanfoundry Global Education & Learning Series – Automata Theory.**

To practice all areas of Automata Theory Problems, __here is complete set of 1000+ Multiple Choice Questions and Answers__.