10. State the meanings of |–, |–
* and |–
+
while accepting strings with NPDA.
|– is used to indicate a single move of an NPDA
|–
* is used to indicate a sequence of zero or more moves
|–
+
is used to indicate a sequence removal in a PDA.
11. What is meant by Empty Production removal in a PDA?
If the empty string does not belong to a language, the there is no way
to eliminate production of the from A → λ from the grammar. If the
empty string belongs to a language, then we can eliminate λ from all
productions for the single production S → λ. In this case we can
eliminate any occurrences of S from the right hand side of productions.
12. What is meant by unit production removal in PDA?
Eliminating productions of the form A B
→ from a CFG is called a
unit production removal in PDA.
13. What is meant by left recursion removal in PDA?
A variable A is left recursive if it occurs in a production of the form
A
Ax
→
for any x V T
∈ ∪
(
) .
* A grammar is left-recursive if it contains at
least one left-recursive variable. Every CFL can be represented by a
grammar that is not left-recursive.
14. What are the Normal Forms of CFGs?
(a) Chomsky Nor mal Form.
(b) Greibach Normal Form.
15. How is an NPDA built from a CFL?
Any string of a CFL has a leftmost derivation. NPDA is set up so that
the stack contents corresponds to this sentential form, every move of the
NPDA represents one derivation step.
16. How is the sentential form obtained while converting a CFG into an
NPDA?
The sentential form is obtained as
[The characters already read] + [symbols on the stack] – [Final z (initial
stack symbol)]
17. What are the two ways in which deterministic pushdown finite acceptor
differs from a non-deterministic finite acceptor?
(a) The transition function δ is single-valued for a DFA, but
multi-valued for an NFA.
(b) An NFA may have λ-transitions.
18. What are the ways in which a non-deterministic pushdown automaton
differs from a Pushdown automata
184
Theory of Automata, Formal Languages and Computation
* and |–
+
while accepting strings with NPDA.
|– is used to indicate a single move of an NPDA
|–
* is used to indicate a sequence of zero or more moves
|–
+
is used to indicate a sequence removal in a PDA.
11. What is meant by Empty Production removal in a PDA?
If the empty string does not belong to a language, the there is no way
to eliminate production of the from A → λ from the grammar. If the
empty string belongs to a language, then we can eliminate λ from all
productions for the single production S → λ. In this case we can
eliminate any occurrences of S from the right hand side of productions.
12. What is meant by unit production removal in PDA?
Eliminating productions of the form A B
→ from a CFG is called a
unit production removal in PDA.
13. What is meant by left recursion removal in PDA?
A variable A is left recursive if it occurs in a production of the form
A
Ax
→
for any x V T
∈ ∪
(
) .
* A grammar is left-recursive if it contains at
least one left-recursive variable. Every CFL can be represented by a
grammar that is not left-recursive.
14. What are the Normal Forms of CFGs?
(a) Chomsky Nor mal Form.
(b) Greibach Normal Form.
15. How is an NPDA built from a CFL?
Any string of a CFL has a leftmost derivation. NPDA is set up so that
the stack contents corresponds to this sentential form, every move of the
NPDA represents one derivation step.
16. How is the sentential form obtained while converting a CFG into an
NPDA?
The sentential form is obtained as
[The characters already read] + [symbols on the stack] – [Final z (initial
stack symbol)]
17. What are the two ways in which deterministic pushdown finite acceptor
differs from a non-deterministic finite acceptor?
(a) The transition function δ is single-valued for a DFA, but
multi-valued for an NFA.
(b) An NFA may have λ-transitions.
18. What are the ways in which a non-deterministic pushdown automaton
differs from a Pushdown automata
184
Theory of Automata, Formal Languages and Computation