CSE 355 Quiz 8
Suppose a PDA pops, but doesn't push, on every transition. Then the
language of the PDA is context-free, but not necessarily regular. - ANS-False
Suppose a PDA pushes, but doesn't pop, on every transition. Then the
language of the PDA is context-free, but not necessarily regular - ANS-False
Suppose a PDA pushes or pops, but doesn't do both or neither, on every transition. Then the
language of the PDA is context-free, but not necessarily regular. - ANS-True
In the formal definition of a PDA, we cannot swap the order of push and pop in the transition
function; we must allow popping before pushing, instead of pushing before popping. - ANS-True
Context-free languages are closed under intersection with regular languages - ANS-True
Suppose I have an algorithm to test if a given CFG accepts some input. Therefore, I also have
an algorithm to test if a given PDA accepts some input. - ANS-True
My friend believes that we can convert a DFA into an equivalent PDA as follows: everything
remains the same as the DFA except for every transition labelled a in
the DFA, we augment the transition to be a, (epsilon) → (epsilon) between the same pair of
states. Is his idea correct?
(a) His idea is correct because DFAs and PDAs recognize the same class of languages.
(b) His idea is correct because DFAs are just PDAs that ignore its stack.
(c) His idea is not correct because this introduces empty transitions, which were not present in
the DFA.
(d) His idea is not correct because there are some languages that a DFA can recognize that a
PDA cannot.
(e) None of the above. - ANS-b
In the conversion of a PDA with n states to a CFG, the number of variables created (without
doing any simplifications) is:
(a) Constant independent of n.
(b) O(n^2) but not a constant independent of n.
(c) O(n^3) but not O(n^2).
(d) Not O(n^3).
(e) Impossible to classify without more information. - ANS-b
In the conversion of a PDA with n states to a CFG, the number of rules created (without doing
any simplifications) is:
(a) Constant independent of n.
Suppose a PDA pops, but doesn't push, on every transition. Then the
language of the PDA is context-free, but not necessarily regular. - ANS-False
Suppose a PDA pushes, but doesn't pop, on every transition. Then the
language of the PDA is context-free, but not necessarily regular - ANS-False
Suppose a PDA pushes or pops, but doesn't do both or neither, on every transition. Then the
language of the PDA is context-free, but not necessarily regular. - ANS-True
In the formal definition of a PDA, we cannot swap the order of push and pop in the transition
function; we must allow popping before pushing, instead of pushing before popping. - ANS-True
Context-free languages are closed under intersection with regular languages - ANS-True
Suppose I have an algorithm to test if a given CFG accepts some input. Therefore, I also have
an algorithm to test if a given PDA accepts some input. - ANS-True
My friend believes that we can convert a DFA into an equivalent PDA as follows: everything
remains the same as the DFA except for every transition labelled a in
the DFA, we augment the transition to be a, (epsilon) → (epsilon) between the same pair of
states. Is his idea correct?
(a) His idea is correct because DFAs and PDAs recognize the same class of languages.
(b) His idea is correct because DFAs are just PDAs that ignore its stack.
(c) His idea is not correct because this introduces empty transitions, which were not present in
the DFA.
(d) His idea is not correct because there are some languages that a DFA can recognize that a
PDA cannot.
(e) None of the above. - ANS-b
In the conversion of a PDA with n states to a CFG, the number of variables created (without
doing any simplifications) is:
(a) Constant independent of n.
(b) O(n^2) but not a constant independent of n.
(c) O(n^3) but not O(n^2).
(d) Not O(n^3).
(e) Impossible to classify without more information. - ANS-b
In the conversion of a PDA with n states to a CFG, the number of rules created (without doing
any simplifications) is:
(a) Constant independent of n.
