Register

Which of the following conversion is not possible (algorithmically)?

14,027 views
3 votes
3 votes
A.    regular grammar to context-free grammar
B.    nondeterministic FSA to deterministic FSA
C.    nondeterministic PDA to deterministic PDA
D.    nondeterministic TM to deterministic TM
User Avatar

1 Answer

Best answer
11 votes
11 votes

The corrcet answer would be C) NPDA to DPDA

Because,

Not every nondeterministic PDA has an equivalent deterministic PDA. Even if you have a nondeterministic PDA that is guaranteed to have a deterministic equivalent, there is no Algorithmic procedure to find it.

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
2 answers
2
techbrk3 asked Nov 16, 2017
510 views
Which of the following is the possible sequence of edges when Prim's algorithm is applied ?
(a,b),(b,c),(a,d),(e,f),(d,g),(c,e) (g,f),(f,c),(g,d),(c,e),(d,b),(d,a) (c,f),(c,e),(e,d),(a,b),(d,g),(b,c) None of the above
(a,b),(b,c),(a,d),(e,f),(d,g),(c,e)(g,f),(f,c),(g,d),(c,e),(d,b),(d,a)(c,f),(c,e),(e,d),(a,b),(d,g),(b,c)None of the above
User Avatar
2 votes
2 votes
3 answers
3
techbrk3 asked Nov 12, 2017
1,953 views
Which of the following is NOT true?
$(a^+)^∗=(a^∗)^+$ $(a^+)^+=aa^+$ $(a^∗)^∗=a^∗$ $aa^+ +a=a^+$
$(a^+)^∗=(a^∗)^+$$(a^+)^+=aa^+$$(a^∗)^∗=a^∗$$aa^+ +a=a^+$
User Avatar
3 votes
3 votes
3 answers
4
ari asked Aug 17, 2015
4,333 views
Which of the following are not equivalent to expression (a + b + c)* ?
Which of the following are not equivalent to expression $(a + b + c)^*$? (A) $(a^* + b^* + c^*)^*$ (B) $\Bigl ( (ab)^* + c^* \Bigr )^*$ (C) $(a^* b^* c^*)^*$ (D) $(a^*b^* + c^*)^*$
Which of the following are not equivalent to expression $(a + b + c)^*$?(A) $(a^* + b^* + c^*)^*$(B) $\Bigl ( (ab)^* + c^* \Bigr )^*$(C) $(a^* b^* c^*)^*$(D) $(a^*b^* + c...
User Avatar
Link Copied!