Register

#gate questions

569 views
0 0 votes

which one true

1. Determining whether context-free grammar is un-decidable

2. Whether a given grammar is context-free is decidable

1 Answer

Voting & Accepting an answer helps improve the community
← Previous · GeneralNext → · TestBook TestSeries ...
← Previous in category · GO Classes CS Test S...Next in category → · Can DCFL be ambiguou...
Position:
Show:

Related questions

1 1 vote
1 answers 1 answer
468
468 views
mili_dhara asked Oct 28, 2024
468 views
Decidability Marathon Part 2 - Theory of Computation | 200 Questions | Rice Theorem | Deepak Poonia
Please explain this statement, not able to get the intuition.
0 0 votes
0 0 answers
469
469 views
Swapnil Naik asked Sep 2, 2018
469 views
Gate-overflow questions
I am confused between the answer of these 2 questions. Here the questions are almost similar, in both of them we need to find out which ones are decidable but both of the...
2 2 votes
2 2 answers
1.5k
1.5k views
iarnav asked Oct 22, 2017
1,472 views
Some Questions on Decidabilty
1) Is it decidable whether a given Turing machine accepts any string at all? That is, is L(M) not equal to ∅? 2) Is it decidable whether a given Turing machine accepts a...
1 1 vote
1 1 answer
43
43 views
GO Classes asked 1 day ago
43 views
GO Classes DPP | GATE CS | Theory of Computation | Decidability
Which of the following languages are recognizable?$\{\langle M\rangle\mid M\ \mathrm{is\ a\ TM\ and}\ L(M)\ \mathrm{is\ finite}\}$ $\{\langle M_1,M_2,w\rangle\mid M_1\ \m...