Whether given CFL is Regular is Decidable?

Question

Which of the following are True?

$S1$: Every NFA can be converted to equivalent PDA

$S2$: Whether a given CFL is Regular is decidable.

1. $S1$                                                 2. $S2$

3. Both                                             4. None

Answer 1

How can a CFL be given? If it is given as the language generated by a CFG, then the problem is undecidable.

The question here is ambiguous.

Comments

Here you are saying "Undecidable" , i also think undecidable , but in which CFL representation it would be decidable?? I think deciding regularity of CFL is always undecidable , untill it is given as FA or Regular Expression.

---

@Arjun : Why is checking the if the CFG is regular undecidable ? I will simply have to look at the grammar and see if all its productions are of form A -> aA/a or B -> bB/b , right ???

---

Question is not to check if a CFG is a regular grammar- this is decidable as you told. But we have to see if a CFG generates a regular language- the grammar here need not be a regular grammar Just that every regular language has an equivalent regular grammar but even other grammar can generate a regular language.

---

@Arjun Sir, The second one is REGULARITY PROBLEM.

right?

---

of CFL.

---

can any1 explain how 1st is true ?

from where we will bring that extra stack ? confused @Arjun sir or any1

Answer 2

Only S1 is decidable.

Checking Regularity for CFLs is UNDECIDABLE problem