Grammars in Theory of Computation: Interactive Learning Quizzes

Question 1

Describe the difference between a lexical analyzer and a parser in a compiler.

Accepted Answer

A lexical analyzer tokenizes the input, while a parser checks the syntax of the tokens.

Answer

A parser tokenizes the input, while a lexical analyzer checks the syntax of the tokens.

Answer

A lexical analyzer and a parser both tokenize the input.

Answer

A lexical analyzer and a parser both check the syntax of the tokens.

Question 2

Which grammar type is not part of the Chomsky hierarchy?

Accepted Answer

Type 5

Answer

Type 0

Answer

Type 1

Answer

Type 2

Question 3

Compare and contrast deterministic and non-deterministic parsing techniques. Discuss their advantages and disadvantages.

Accepted Answer

Deterministic techniques (e.g., LL(k), LR(k)) follow strict rules, offering efficiency and predictability. However, they may struggle with ambiguous or complex grammars.

Accepted Answer

Non-deterministic techniques (e.g., recursive descent, backtracking) explore multiple paths, providing flexibility for complex grammars. However, they can be less efficient and resource-intensive.

Answer

Deterministic techniques are generally more efficient due to their structured approach.

Answer

Non-deterministic techniques offer greater flexibility in handling complex grammars.

Question 4

Which grammar type falls outside the Chomsky hierarchy?

Accepted Answer

Stochastic grammar

Answer

Regular grammar

Answer

Context-free grammar

Question 5

Which statement best describes the role of parsing in a compiler?

Accepted Answer

Parsing verifies the syntactic correctness of source code. For example, it checks for missing semicolons in a Java program.

Answer

Parsing is not involved in compilation. Its main function is to optimize compiled code efficiency.

Answer

Parsing generates machine code directly from source code for execution.

Answer

Parsing is only used to identify semantic errors in source code.

Question 6

In LL(1) parsing, which operation is crucial?

Accepted Answer

Predictive Parsing

Answer

Top-Down Parsing

Answer

Bottom-Up Parsing

Answer

LR Parsing

Question 7

What is the fundamental concept behind regular expressions?

Accepted Answer

Using symbols and operations to represent patterns in language definition.

Answer

Explicitly listing all strings in a language definition.

Answer

Defining languages using production rules.

Answer

Defining languages using state transition diagrams.

Question 8

Which property is characteristic of context-free grammars?

Accepted Answer

Both sides of production rules can contain both terminal and non-terminal symbols.

Answer

The left-hand side of production rules can contain only non-terminal symbols.

Answer

The right-hand side of production rules can contain only terminal symbols.

Answer

Production rules can be applied in any order.

Question 9

What is the primary purpose of using a parse tree?

Accepted Answer

To represent the hierarchical structure of a sentence.

Answer

To determine the validity of a sentence.

Answer

To identify errors in a program.

Answer

To translate a sentence from one language to another.

Question 10

Which option is NOT a widely used parsing technique?

Accepted Answer

Inside-out parsing

Answer

Top-down parsing

Answer

Bottom-up parsing

Answer

Dynamic programming parsing

Question 11

What is the closure property of regular languages under concatenation?

Accepted Answer

The concatenation of two regular languages is always a regular language.

Answer

The concatenation of two regular languages is not always a regular language.

Answer

The concatenation of a regular language with a non-regular language is always a regular language.

Answer

Regular languages are not closed under concatenation.

Question 12

In a context-free grammar, what is the defining characteristic of the left-hand side of a production rule?

Accepted Answer

It contains a single non-terminal symbol.

Answer

It contains multiple non-terminal symbols.

Answer

It contains a mix of terminal and non-terminal symbols, but only one non-terminal symbol.

Answer

It must always contain at least one terminal symbol.

Question 13

Which type of grammar generates strings in a hierarchical, top-down manner?

Accepted Answer

Type 0 grammar

Answer

Type 1 grammar

Answer

Type 2 grammar

Answer

Type 3 grammar

Question 14

Which property is unique to regular grammars?

Accepted Answer

Their productions follow the format: A -> a or A -> aB

Answer

They can generate all recursively enumerable languages.

Answer

They can generate all context-free languages.

Answer

They can generate all context-sensitive languages.

Question 15

Which parsing technique involves starting with the input string and successively building a parse tree bottom-up?

Accepted Answer

Bottom-up parsing

Answer

Top-down parsing

Answer

Recursive descent parsing

Answer

Earley parsing

Question 16

Which property is characteristic of context-sensitive grammars?

Accepted Answer

Their productions take the form: A -> alpha or A -> alphaBbeta

Answer

They can generate all recursively enumerable languages.

Answer

They can generate all context-free languages.

Answer

They can generate all regular languages.

Question 17

In a context-free grammar for the language of balanced parentheses, which production is recursive?

Accepted Answer

S -> (S)

Answer

S -> )

Answer

S -> epsilon

Question 18

Which of the following properties is unique to context-sensitive grammars?

Accepted Answer

Their productions can depend on the surrounding context.

Answer

They can generate non-context-free languages.

Answer

They have an infinite number of production rules.

Answer

They can be parsed using top-down parsing techniques.

Question 19

In the Chomsky hierarchy, which grammar type has the highest level?

Accepted Answer

Type 0

Answer

Type 1

Answer

Type 2

Answer

Type 3

Question 20

Among the following options, which correctly defines a formal grammar?

Accepted Answer

A 4-tuple consisting of non-terminals, terminals, productions, and start symbol

Answer

A tree-like structure derived from a sentence

Answer

A Chomsky hierarchy classification

Answer

A set of production rules only

Question 21

Among the following, which is an application of context-free grammars?

Accepted Answer

Representing the syntax of programming languages

Answer

Image recognition

Answer

Network routing

Answer

Database modeling

Question 22

What is the primary purpose of a start symbol in a grammar?

Accepted Answer

Identifying the initial non-terminal in a derivation

Answer

Indicating the end of a valid sentence

Answer

Representing the empty string

Answer

Enforcing the grammar's Chomsky type

Question 23

What is the significance of the Chomsky hierarchy in computer science?

Accepted Answer

It provides a framework for classifying formal languages based on their generative power.

Answer

It allows for efficient parsing of all types of languages.

Answer

It helps design new programming languages with specific properties.

Question 24

What is the main difference between a generative grammar and a recognition grammar?

Accepted Answer

A generative grammar can produce strings in the language, while a recognition grammar can only determine if a given string is in the language.

Answer

A generative grammar is more powerful than a recognition grammar.

Question 25

In a grammar, the start symbol represents:

Accepted Answer

The root of the parse tree.

Answer

The end of the grammar definition.

Answer

The first token in the input string.

Answer

A mechanism to prevent infinite recursion during parsing.

Question 26

Regular grammars are characterized by which property?

Accepted Answer

They can generate all regular languages.

Answer

They cannot generate any recursive languages.

Answer

They can generate all context-free languages.

Answer

Their productions are limited to unit productions.

Question 27

Which of the following is NOT an advantage of using grammars in computer science?

Accepted Answer

Improved code readability

Answer

Syntax analysis

Answer

Efficient parsing algorithms

Answer

Formal specification of languages

Question 28

The purpose of a derivation tree in a grammar is to:

Accepted Answer

Represent the steps taken to generate a string from the grammar.

Answer

Show only the leftmost or rightmost derivations.

Answer

Determine if a string is generated by the grammar.

Question 29

Which operation, when applied to a set of strings, results in a closure?

Accepted Answer

Taking the set of all prefixes of the strings.

Answer

Taking the set of all substrings of the strings.

Answer

Taking the set of all suffixes of the strings.

Answer

Taking the set of all reversals of the strings.

Question 30

Epsilon productions in a grammar are used for:

Accepted Answer

Generating empty strings.

Answer

Making the grammar more deterministic.

Answer

Reducing the number of productions in the grammar.

Answer

Increasing the expressive power of the grammar.

Question 31

Ambiguous grammars are characterized by:

Accepted Answer

Multiple parse trees for the same string.

Answer

An inability to generate any valid strings.

Answer

Always being more difficult to parse than unambiguous grammars.

Question 32

Which type of grammar allows for the generation of any string in a language, regardless of meaning or structure?

Accepted Answer

Unrestricted grammar

Answer

Context-sensitive grammar

Answer

Context-free grammar

Answer

Regular grammar

Question 33

In the Chomsky Hierarchy, which grammar type is characterized by productions of the form A → aB, where A and B are non-terminal symbols and a is a terminal symbol?

Accepted Answer

Regular grammar

Answer

Context-sensitive grammar

Answer

Context-free grammar

Answer

Unrestricted grammar

Question 34

Which of the following is NOT a limitation of context-free grammars?

Accepted Answer

Using context-dependent rules in productions.

Answer

They can be represented using a parse tree.

Answer

Productions can be in the form A → α, where A is a non-terminal and α is a string of terminals and non-terminals.

Answer

They can be used to describe programming language syntax.

Question 35

What is the purpose of a parser in the context of grammars?

Accepted Answer

To determine if a given string can be generated by a specific grammar.

Answer

To generate all possible strings in a language.

Answer

To convert a grammar into a different format.

Question 36

Which parsing technique uses a table to store possible derivations for all prefixes of an input string?

Accepted Answer

CYK Algorithm

Answer

Shift-Reduce Parsing

Answer

Top-Down Parsing

Answer

Recursive Descent Parsing

Question 37

Which type of grammar is typically used to describe the syntax of programming languages?

Accepted Answer

Context-Free Grammar

Answer

Unrestricted Grammar

Answer

Context-Sensitive Grammar

Answer

Regular Grammar

Question 38

What is the primary difference between a top-down and bottom-up parsing strategy?

Accepted Answer

Top-down starts with the start symbol and tries to derive the input string, while bottom-up starts with the input string and tries to reduce it to the start symbol.

Answer

Top-down uses a table, while bottom-up uses a stack.

Question 39

Which of the following is a common application of grammars in computer science?

Accepted Answer

Compilers and interpreters for programming languages

Answer

Image processing and computer vision

Answer

Data mining and machine learning

Question 40

Which of the following is the most restrictive type of grammar in the Chomsky hierarchy?

Accepted Answer

Regular Grammar

Answer

Context-Free Grammar

Answer

Context-Sensitive Grammar

Answer

Type 0 Grammar

Question 41

Which of the following is a key characteristic of context-free grammars?

Accepted Answer

Production rules are of the form A -> α, where A is a non-terminal and α is a string of terminals and non-terminals.

Answer

Production rules can be circular.

Question 42

Which of the following is a limitation of top-down parsing techniques?

Accepted Answer

They can lead to infinite recursion when the grammar is left-recursive.

Answer

They can only be used for context-free grammars.

Answer

They require the construction of a parse table.

Question 43

What does the Chomsky Normal Form (CNF) for a context-free grammar ensure?

Accepted Answer

All production rules are either of the form A -> BC or A -> a, where A, B, and C are non-terminals and a is a terminal.

Answer

The grammar is in LL(1) form.

Question 44

What is the role of a start symbol in a grammar?

Accepted Answer

It is the non-terminal symbol that generates all other symbols in the grammar.

Answer

It is a non-terminal symbol that can appear on both sides of production rules.

Answer

It is a terminal symbol that marks the end of a string.

Question 45

Which type of grammar allows for the generation of all regular languages and is often used in compiler design?

Accepted Answer

Regular grammar

Answer

Context-free grammar

Answer

Context-sensitive grammar

Question 46

Which of the following grammars is the most expressive, capable of describing all recursively enumerable languages?

Accepted Answer

Type 0 (Unrestricted) grammar

Answer

Type 3 (Regular) grammar

Answer

Type 1 (Context-sensitive) grammar

Answer

Type 2 (Context-free) grammar

Question 47

Given the grammar with production rules S -> aSb | ε, what is the language it generates?

Accepted Answer

The language of all strings with an equal number of 'a' and 'b', where 'a' precedes 'b'.

Answer

The language of all strings with an equal number of 'a' and 'b', in any order.

Answer

The language of all strings with any number of 'a' and 'b'.

Question 48

Which parsing technique builds a parse tree by starting from the root node and expanding the tree using the grammar rules?

Accepted Answer

Top-down parsing

Answer

Shift-reduce parsing

Answer

Recursive descent parsing

Answer

Bottom-up parsing

Question 49

What is the key difference between a context-free grammar and a regular grammar?

Accepted Answer

Context-free grammars allow for recursion, while regular grammars do not.

Answer

Context-free grammars are more efficient than regular grammars.

Answer

Regular grammars are more expressive than context-free grammars.

Question 50

Which of the following languages can be recognized by a finite automaton?

Accepted Answer

The language of all strings with an even number of 0s.

Answer

The language of all strings with balanced parentheses.

Answer

The language of all palindromes.

Question 51

A grammar is said to be ambiguous if...

Accepted Answer

...it allows for multiple parse trees for a single string.

Answer

...it includes redundant production rules.

Answer

...it generates an infinite number of strings.

Question 52

Which of the following is NOT a characteristic of a context-sensitive grammar?

Accepted Answer

The left-hand side of a production rule can be empty.

Answer

The right-hand side of a production rule can be replaced by another string with the same length or longer.

Answer

The production rules can depend on the context of the symbols on the left-hand side.

Question 53

What is the primary use of a parse tree?

Accepted Answer

To represent the derivation of a string from a grammar.

Answer

To define the formal language of a grammar.

Answer

To determine the complexity of a grammar.

Question 54

Which parsing technique is typically used in compiler design to efficiently parse programming languages?

Accepted Answer

LR parsing

Answer

LL parsing

Answer

Recursive descent parsing

Answer

Top-down parsing