Register

Decidable and Undecidable problems of automata

4,015 views
0 votes
0 votes
Please list down all the decidable and undecidable problems for FA, PDA, TM.

Since there isnt a single place where all are listed.
User Avatar

1 Answer

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
daksirp asked Jul 9, 2018
693 views
decidable and undecidable problem : https://gatecse.in/grammar-decidable-and-undecidable-problems/
Soutce : https://gatecse.in/grammar-decidable-and-undecidable-problems/ Why L(G1) ⋂ L(G2) = Φ ?? is undecidable for dcfl, cfl etc ?? please explain it anyone
Soutce : https://gatecse.in/grammar-decidable-and-undecidable-problems/Why L(G1) ⋂ L(G2) = Φ ?? is undecidable for dcfl, cfl etc ?? please explain it anyone
User Avatar
1 votes
1 votes
0 answers
2
shivangi5 asked Sep 21, 2017
537 views
Decidable and undecidable problems
Please explain by giving example... 1.All undecidable problems are NP-Hard, but all NP-Hard problems are not undecidable. 2.NP and NPC problems can all be decided by a TM and hence are recursive.
Please explain by giving example...1.All undecidable problems are NP-Hard, but all NP-Hard problems are not undecidable.2.NP and NPC problems can all be decided by a TM a...
User Avatar
0 votes
0 votes
0 answers
3
Mk Utkarsh asked Sep 15, 2018
566 views
Decidable / Undecidable (Acceptance of CFL)
A Turing Machine accepts a language if its DCFL but rejects if it's a non deterministic CFL
A Turing Machine accepts a language if its DCFL but rejects if it's a non deterministic CFL
User Avatar
6 votes
6 votes
1 answer
4
himgta asked Feb 15, 2018
2,811 views
why completeness problem in case of DCFL is decidable, & it is undecidable in case of CFL?
User Avatar
Link Copied!