# Theory of Computation: Question Set – 09

#### What is a parse tree?

A parse tree is a graphical representation of the way in which the production rules of a grammar are used to generate a particular string in the language. The tree consists of nodes representing the symbols in the string, and edges representing the application of production rules to generate those symbols. Parse trees can be used to analyze the structure of a string in a formal language and to generate code from a high-level language specification.

#### What is the difference between a derivation and a parse?

A derivation is the sequence of production rules that are applied to generate a string in a formal language, while a parse is the process of constructing a parse tree for that string. Derivations can be used to analyze the structure of a string in a formal language, while parses are often used to generate code from a high-level language specification.

#### What is the difference between a left-recursive and a right-recursive grammar?

A left-recursive grammar is a grammar in which the leftmost symbol on the right-hand side of a production rule is the same as the nonterminal symbol on the left-hand side, while a right-recursive grammar is a grammar in which the rightmost symbol on the right-hand side of a production rule is the same as the nonterminal symbol on the left-hand side. Left-recursive grammars can cause problems when parsing with a recursive descent parser, while right-recursive grammars can cause problems with backtracking in a top-down parser.

#### What is the pumping lemma for context-free languages?

The pumping lemma for context-free languages is a theorem that states that all context-free languages have a certain property that can be used to show that they are not regular. Specifically, the pumping lemma states that if a language L is context

#### What is a finite automaton?

A finite automaton is a mathematical model used to recognize regular languages. It consists of a finite set of states, a set of input symbols, a transition function that maps each state and input symbol to a new state, a start state, and a set of accept states.

#### What is the difference between a deterministic finite automaton (DFA) and a nondeterministic finite automaton (NFA)?

A deterministic finite automaton (DFA) is a type of finite automaton where each transition is uniquely determined by the current state and input symbol. A nondeterministic finite automaton (NFA) is a type of finite automaton where each transition can have multiple possible outcomes for the same input symbol and current state.

#### What is the difference between a complete and an incomplete automaton?

A complete automaton is an automaton where for each state and each input symbol, there is a defined transition. An incomplete automaton is an automaton where there may be some states and input symbols where no transition is defined.

#### What is the language recognized by a finite automaton?

The language recognized by a finite automaton is the set of all strings that, when read from the start state, cause the automaton to end up in an accept state.

#### How can you convert a NFA to a DFA?

To convert a NFA to a DFA, you can use the subset construction algorithm. The basic idea is to represent each state of the DFA as a set of states from the NFA, and then compute the transitions between DFA states by computing the set of NFA states reachable from the current set of DFA states.

#### Can you give an example of a regular language that cannot be recognized by a finite automaton?

Such language does not exist. All regular languages have equivalent finite automata representation.