551 views
1 votes
1 votes

Need Explaination :

_________________________________________________________________

" Whether L(G) is a regular language? "-It is undecidable

1)question is why is it undecidable?

___________________________________________________________________

" Whether L(G) is a CFL? (trivial) "- it is decidable

2)question is why is it decidable?

1 Answer

2 votes
2 votes

See, First You must describe "What is $G$?"

If $G$ is any Type-0 Grammar, then Both Problems i.e. Deciding whether $L(G)$ is CFL or Regular are Undecidable.

If $G$ is any Type-1 Grammar, then also Both Problems i.e. Deciding whether $L(G)$ is CFL or Regular are Undecidable.

If $G$ is any Type-2 Grammar, then Problem First i.e. Deciding whether $L(G)$  is Regular is Undecidable. But Deciding Whether $L(G)$ is CFL is Decidable (Trivial Since Every Type-2 Grammar always generates a CFL But may or may not generate a Regular language)

If $G$ is any Type-3 Grammar, then Both Problems i.e. Deciding whether $L(G)$ is CFL or Regular are Decidable.

So, It Very much depends on the Domain on/in which you're asking the Problems.


Coming to Why Deciding Whether $L(G)$ is Regular or CFL is Undecidable When $G$ is any Type-0 Grammar ?

It's because of Rice's Theorem. Since these are Non-trivial Properties for RE languages.  

edited by

Related questions

0 votes
0 votes
0 answers
3
Na462 asked Jan 21, 2019
713 views
0 votes
0 votes
0 answers
4
Ayush Upadhyaya asked Jan 13, 2019
403 views
From http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf $L_{26}=\{<M>|$ M is a TM such that both L(M) and $\lnot L(M)$ are infinite $\}$I was unable to get...