Register

Decidability and Undecidability

• edited by
403 views
0 0 votes
helloo just got a qstn, is universality problem for cfl decidable or undecidable? in toc sir taught it is deccidable , but in the chart sir shown it was writen undecidable. i am talking about 2024 lecture though.... even in gate pyqs it is writen undecidable in many parts...

1 Answer

Voting & Accepting an answer helps improve the community
← Previous · PipeliningNext → · how to get detailed ...
← Previous in category · #self doubtNext in category → · TOC doubt
Position:
Show:

Related questions

0 0 votes
0 0 answers
294
294 views
Abhipsa Panda asked May 24, 2022
294 views
Decidability and undecidability
How is equality problem for DCFL decidable?
2 2 votes
1 answers 1 answer
641
641 views
aftab0711 asked Aug 27, 2024
641 views
Decidability/Undecidability Question on CGF
Which of the following language is/are Turing decidable? 1. L = { <G1, G2 | G1 & G2 are regular grammar and L(G1) ⊆ L(G2)} 2. L = { <G, R | G is a CFG & R is a regular ex...
11 11 votes
1 1 answer
3.3k
3.3k views
Balaji Jegan asked Jul 12, 2018
3,264 views
Decidability Vs Semi-Decidability Vs Undecidability Self Doubt
Please tell whether the following is Decidable, Semi-decidable or UndecidableA turing machine halts after running for exactly k stepsA turing machine halts after running ...
0 0 votes
0 0 answers
1.2k
1.2k views
Balaji Jegan asked Jun 20, 2018
1,244 views
Semi-decidability Vs Undecidability
Let L1 and L2 be 2 languages generated by an Unrestricted Grammar. I know that none of the following are decidable. But which of them are semi-decidable and which are Und...