# Automata Theory Questions and Answers – CFL- Other Normal Forms

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

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

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

Explanation: Pentonnen Normal form(for Unrestricted grammars) is a special case where there is a slight modification in the format of Kuroda Normal form.
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

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

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
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

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

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(n3 .|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

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

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

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]