This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “CFL- Other Normal Forms”.

1. The following format of grammatical notation is accepted by which of the following:

AB->CD

A->BC or

A->B or

A->a

where A, B, C, D are non terminal symbols and a is a terminal symbol.

a) Greibach Normal Form

b) Chomsky Nrmal Form

c) Kuroda Normal Form

d) None of the mentioned

View Answer

Explanation: Linearly Bounded grammar or Kuroda Normal Form allows the following format of grammatical analysis:

AB->CD

A->BC or

A->B or

A->a

2. Every Kuroda Normal form grammar generates ___________

a) Context free grammar

b) Context sensitive grammar

c) Unrestricted grammar

d) None of the mentioned

View Answer

Explanation: Every context sensitive grammar which does not produce an empty string can be generated by a grammar in Kuroda Normal form.

3. Which of the following can generate Unrestricted grammars?

a) Pentonnen Normal form

b) Floyd Normal form

c) Greibach Normal form

d) None of the mentioned

View Answer

Explanation: Pentonnen Normal form(for Unrestricted grammars) is a special case where there is a slight modification in the format of Kuroda Normal form.

AB->AD

A->BC

A->a

4. Given a grammar in GNF and a derivable string in the grammar with the length n, any ___________will halt at depth n.

a) top-down parser

b) bottom-up parser

c) multitape turing machine

d) none of the mentioned

View Answer

Explanation: Given a grammar in GNF and a derivable string in the grammar with the length n, any top-down parser will halt at depth n. As the parameter ‘depth’ is mentioned, we will use a top-down parser. Example-LL parser.

5. Which of the following grammars is similar to Floyd Normal form?

a) Backus Naur Form

b) Kuroda Normal Form

c) Greibach Normal Form

d) Chomsky Normal Form

View Answer

Explanation: Donald Knuth implied a BNF” syntax in which all definitions have such a form may be said to be in ”Floyd Normal Form”.

A->B|C

A->BC

A->a

6. Which among the following can parse a context free grammar?

a) top down parser

b) bottom up parser

c) CYK algorithm

d) all of the mentioned

View Answer

Explanation: We use certain algorithms to parse a context free grammar which include the most popular CYK algorithm which employs the concept of bottom up parsing and dynamic parsing.

7. The standard version of CYK algorithm operates only on context free grammars in the following form:

a) Greibach Normal form

b) Chomsky Normal form

c) Backus Naur form

d) All of the mentioned

View Answer

Explanation: It requires the presence of a context free grammar into Chomsky Normal form to operate. However, every context free grammar can be converted into CNF for keeping the sense of grammar equivalent.

8. The __________ running time of CYK is O(n^{3} .|G|)

where n is the length of the parse string and |G| is the size of the context free grammar G.

a) worst

b) best

c) average

d) none of the mentioned

View Answer

Explanation: This is the worst case running time of CYK and and this makes it one of the most efficient algorithms for recognizing general context free languages in practice.

9. Which of the following is true for Valiants algorithm?

a) an extension of CYK

b) deals with efficient multiplication algorithms

c) matrices with 0-1 entries

d) all of the mentioned

View Answer

Explanation: Valiants algorithm is actually an extention of CYK which even computes the same parsing table yet he showed another method can be utilized fro performing this operation.

10. Which among the following is a correct option in format for representing symbol and expression in Backus normal form?

a) <symbol> ->expression

b) <symbol>::=_expression_

c) <symbol>=<expression>

d) all of the mentioned

View Answer

Explanation: <symbol>::=_expression_ is the correct representation where <symbol> is a non terminal, and expression consist of one or more sequence of symbols, more sequence are separated by |, indicating a choice.

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

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