Question:
Which of the following is FALSE?
Which of the following is FALSE?
Show Hint
Nondeterministic PDAs and deterministic PDAs have different expressive powers. Not all nondeterministic PDAs can be converted into deterministic ones.
Updated On: Jun 16, 2025
- Every NFA can be converted to an equivalent PDA
- Complement of every context free language is recursive
- There is a unique minimal DFA for every regular language
- Every nondeterministic PDA can be converted to an equivalent deterministic PDA
Show Solution
Verified By Collegedunia
The Correct Option is D
Solution and Explanation
It is FALSE that every nondeterministic PDA (NPDA) can be converted into an equivalent deterministic PDA (DPDA). The class of languages recognized by a DPDA is strictly smaller than that recognized by an NPDA. In contrast, all the other statements are true: every NFA can be converted to a PDA, the complement of every context-free language is recursive, and there is a unique minimal DFA for every regular language.
Was this answer helpful?
0
0
Top AP PGECET Theory of Computation Questions
- The minimum number of states in a DFA accepting \( L = \{ w | w \text{ ends with } 01 \} \) over \( \Sigma = \{0, 1\} \) is _______ .
- The maximum number of transitions which can be performed over a state in a DFA? \( \Sigma = \{a, b, c\} \)
- Which of the following is a regular language?
- The minimum number of nodes in a DFA that recognizes strings over \( \{a, b\} \) with length mod 3 = 0 are _______ .
- If the production rules are given as:
\( S \to XY | W \)
\( X \to aXb | \epsilon \)
\( Y \to cY | \epsilon \)
\( W \to aWc | bZ | \epsilon \)
\( Z \to bZ | \epsilon \)
Then the language generated by these rules is _______ .
View More Questions
Top AP PGECET Regular expressions and finite automata Questions
- The minimum number of states in a DFA accepting \( L = \{ w | w \text{ ends with } 01 \} \) over \( \Sigma = \{0, 1\} \) is _______ .
- The maximum number of transitions which can be performed over a state in a DFA? \( \Sigma = \{a, b, c\} \)
- Which of the following is a regular language?
- The minimum number of nodes in a DFA that recognizes strings over \( \{a, b\} \) with length mod 3 = 0 are _______ .
- Let \( P \) be a regular language and \( Q \) be a context free language such that \( Q \) is a subset of \( P \). Then which of the following is ALWAYS regular?
Top AP PGECET Questions
- If 125V is applied across a 250V, 100W incandescent bulb, the power consumed will be _____ .
- The power consumed by a coil is 300 watts when connected to a 30V DC source and 108 watts when connected to a 30V AC source. The reactance of the coil is ____ .
The supply voltage magnitude \( |V| \) of the circuit shown below is ____ .
A two-port network is defined by the relation
\(\text{I}_1 = 5V_1 + 3V_2 \)
\(\text{I}_2 = 2V_1 - 7V_2 \)
The value of \( Z_{12} \) is:- Which of the following theorems is the dual of Norton’s theorem?
View More Questions