Theory of Computation: Question Set – 19

Theory of Computation: Question Set – 19

What is the difference between LL and LR parsing in the context of context-free grammars?

LL (left-to-right, leftmost derivation) parsing is a top-down parsing technique that generates a leftmost derivation of a string by repeatedly expanding the leftmost nonterminal in the current derivation. LR (left-to-right, rightmost derivation) parsing is a bottom-up parsing technique that generates a rightmost derivation of a string by repeatedly reducing the rightmost substring that matches a production rule. LL parsing is typically used for simple grammars, while LR parsing is more powerful and can handle a wider range of grammars.

What is the pumping lemma for context-free languages?

The pumping lemma for context-free languages is a property that applies to all context-free languages. It states that if a string in a context-free language is long enough, it can be split into three parts such that the middle part can be repeated any number of times and still be in the language. The pumping lemma can be used to prove that certain languages are not context-free.

What is a context-sensitive grammar?

A context-sensitive grammar is a type of formal grammar in which the production rules are of the form αAβ -> αγβ, where A is a nonterminal symbol, α and β are strings of zero or more terminal and nonterminal symbols, and γ is a string of one or more symbols. Context-sensitive grammars are more powerful than context-free grammars, but are also more complex to work with.

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

A context-free language is a language that can be generated by a context-free grammar, while a regular language is a language that can be generated by a regular expression or a finite automaton. Context-free languages can have more complex structures than regular languages, such as nested parentheses or balanced parentheses, but they are also more difficult to parse.

What is the pumping lemma for regular languages?

The pumping lemma for regular languages is a property that applies to all regular languages. It states that if a string in a regular language is long enough, it can be split into three parts such that the middle part can be repeated any number of times and still be in the language. The pumping lemma can be used to prove that certain languages are not regular.

What is the difference between a leftmost derivation and a rightmost derivation in the context of context-free grammars?

A leftmost derivation is a way of deriving a string from a context-free grammar by always replacing the leftmost nonterminal symbol in the current string with the right-hand side of a production rule. A rightmost derivation is similar, but always replaces the rightmost nonterminal symbol in the current string with the right-hand side of a production rule. Leftmost and rightmost derivations can produce different parse trees for the same string, but they always produce the same final string.

What is the role of nonterminal symbols in a context-free grammar?

Nonterminal symbols in a context-free grammar represent abstract syntactic categories that can be expanded into sequences of terminal and nonterminal symbols. Nonterminal symbols are typically used to represent parts of a sentence or phrase that have a common structure, such as noun phrases or verb phrases.

What is the difference between a recursive and a non-recursive context-free grammar?

A recursive context-free grammar is one that contains at least one production rule of the form A -> αAβ, where A is a nonterminal symbol and α and β are strings of zero or more terminal and nonterminal symbols. This allows the grammar to generate infinite strings by recursively expanding a nonterminal symbol. A non-recursive context-free grammar, on the other hand, does not allow for this kind of recursive expansion and can only generate finite strings.