Register

DECIDABILITY

1,414 views

1 Answer

0 votes
0 votes
Complement of CFL is Not CFL -- Decidable

Complement of Recursive is Recursive  - Decidable

ambiguity of grammar is not decidable

Grammar in regular/CFL/rel decidable or not?  -- try producing string from the grammar if they all are regular then it's regular grammar unless they are not and same with other language.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
2 answers
1
iarnav asked Oct 30, 2017
2,216 views
Decidability Question
a) language accepted by a CFG(Context free grammar) is nonempty. is it D or UD?
a) language accepted by a CFG(Context free grammar) is nonempty.is it D or UD?
User Avatar
3 votes
3 votes
2 answers
2
amrendra pal asked Aug 22, 2017
1,054 views
decidability
C = { <G,k> | G is a CFG and L(G) contains exactly k strings where k>=0 or k=∞ } . Then C will be- a) decidable b) Turing unrecognizable c) Recursive enumerable d) undecidable
C = { <G,k | G is a CFG and L(G) contains exactly k strings where k>=0 or k=∞ } . Then C will be-a) decidableb) Turing unrecognizablec) Recursive enumerabled) undecidab...
User Avatar
Link Copied!