What is the difference between a left-recursive and a right-recursive production rule?

A left-recursive production rule is one of the form A -> Aα, where A is a nonterminal symbol and α is a string of zero or more terminal and nonterminal symbols. A right-recursive production rule is similar, but has the form A -> αA. The difference is in the order in which the nonterminal symbols are expanded: in a left-recursive rule, the nonterminal symbol is expanded before the rest of the string, while in a right-recursive rule, the nonterminal symbol is expanded after the rest of the string.

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

A context-free grammar has production rules of the form A -> α, where A is a nonterminal symbol and α is a string of zero or more terminal and nonterminal symbols. A context-sensitive grammar, on the other hand, has production rules 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 terminal and nonterminal symbols. Context-sensitive grammars are more powerful than context-free grammars, but also more difficult to work with.

What is the difference between a leftmost and a rightmost derivation tree?

A leftmost derivation tree is a derivation tree that follows the leftmost expansion of nonterminal symbols in each step, while a rightmost derivation tree follows the rightmost expansion. In a leftmost derivation tree, the leftmost nonterminal symbol is always expanded first, while in a rightmost derivation tree, the rightmost nonterminal symbol is expanded first. These trees can be used to determine the order in which production rules were applied to generate a string.

What is a pushdown automaton (PDA)?

A pushdown automaton (PDA) is a type of automaton that extends a finite state machine with an additional stack. It can read input symbols, push and pop symbols onto the stack, and move through a finite set of states. PDAs are used to recognize context-free languages and can be more powerful than finite state machines.

What is the difference between a deterministic PDA and a non-deterministic PDA?

A deterministic PDA (DPDA) is a pushdown automaton in which each state has only one possible transition for each input symbol and stack symbol. A non-deterministic PDA (NPDA) can have multiple possible transitions for each input symbol and stack symbol. This means that an NPDA can be in multiple states at once, making it more powerful than a DPDA.

How does a PDA recognize a string?

A PDA recognizes a string by using its finite state machine and stack to keep track of its current state and the symbols on its stack. As it reads each input symbol, it may push or pop symbols from the stack and transition to a new state. If it reaches the end of the string and is in an accepting state with an empty stack, it accepts the string. Otherwise, it rejects the string.

How can you convert a non-deterministic PDA to a deterministic PDA?

One way to convert a non-deterministic PDA to a deterministic PDA is to use the subset construction. The idea is to create a new state for each subset of the original states of the NPDA, and then determine the transitions of the new DPDA based on the transitions of the original NPDA. This construction can be used to convert any non-deterministic finite automaton to a deterministic finite automaton, not just PDAs.

What is the language recognized by a PDA?

The language recognized by a PDA is the set of all strings that can be accepted by the PDA. This language is a context-free language, since PDAs can recognize context-free languages.

What is the language generated by a context-free grammar?

The language generated by a context-free grammar is the set of all strings that can be derived from the start symbol of the grammar using its productions.