The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
83 views
1)Let G is CFG. Whether L(G) is CFL.

Q)Is it decidable or not?

2)Let G is CFG and unambiguous. Whether L(G) is CFL.

Q)Is it decidable or not?
asked in Theory of Computation by Veteran (86.7k points) | 83 views

2 Answers

+1 vote

Both the Problems are Trivially Decidable. We know that Every CFG (Doesn't matter whether it is ambiguous or unambiguous ) generates a CFL . So, If someone comes to you and asks you "$G$ is a CFG, Will $L(G)$ be CFL ??" ..You can just trivially say "Yes". 

Or another way to understand it is as following :

Decidable problems mean that there is Some Algorithm to solve them (Though Algorithm word is not precisely defined but I am assuming the same meaning of this word as you know it)..So, This Problem is decidable because I can write an Algorithm for this Problem... My Algorithm will take whatever CFG $G$ you pass as input and Will (without calculating/doing anything) just simply output "Yes". $O(1)$ time algorithm(vacuous algorithm).. 


When the Domain is Unrestricted grammars i.e. $G$ can be any Type-0 grammar and then if it is asked "whether $L(G)$ is CFL or not" ....is Undecidable (Because of Rice's theorem)

answered by Boss (13.2k points)
0 votes

it is better to learn this table for gate exam becz many question are direct regarding closure nd decidability.

ist one is membership hence fromtable it is decidable

2nd one is ambiguity of grammar which is undecidable

answered by Active (2.3k points)
+1
This is the problem of learning tables :) You already got the first one wrong despite it being a direct question. It is not the membership problem of $CFG.$
0
Sir plz explain it.
0
First one is a trivial problem because every CFG generates a CFL. Hence, it becomes decidable. (Ideally one should never ask if a trivial problem is decidable - this shows that one is not understanding the problem)
0

ok, we can ask specifically for DCFG or NCFG

but not for CFG

right?

And for NCFG it will be undecidable

rt?

because "G is NCFG. Whether L(G) is CFL."

here we cannot decide the part of DCFL

0
THEN SIR FOR MEMBERSHIP PROBLEM THERE SHOULD be the sign of "belongs to"????
0

Both are Decidable (Trivially/vacuously) problems.

THEN SIR FOR MEMBERSHIP PROBLEM THERE SHOULD be the sign of "belongs to"????

Membership problem for CFLs states that "Given a PDA $P$ or Type-2 Grammar $G$, and some string $w$ then finding whether $w$ belongs to $L(G) $ or $L(P)$ or not.... " .... It is Decidable too. But the asked problems in the Question are Not membership problems.

0

And for NCFG it will be undecidable

No. We know whether  $G$ is NCFG or DCFG or CFG whatever... $L(G)$ is always CFL...So, Trivially decidable.

"G is NCFG. Whether L(G) is CFL."

Decidable. 

But if you ask that "Given $G$ is some CFG and whether $L(G)$ will be DCFL or Not" ...that would be Undecidable.  

0

First one is a trivial problem because every CFG generates a CFL.

Second one is also Trivial. Unambiguous or not..If $G$ is CFG then $L(G)$ will Always be CFL. 

0
But we know ambiguous grammar is undecidable. right?
0

But we know ambiguous grammar is undecidable. right?

When we make a Table(like the one attached with the answer) or Short notes etc, we just write the key words like Ambiguity, Universality, Finiteness etc... Not the Whole statement of the Problem.

So, The "ambiguous grammar" problem that you are thinking is Undecidable goes like this "Given a CFG $G$, Finding whether $G$ is ambiguous or Not" ... This problem is Undecidable.

So, Making short notes and just writing key words is not bad... But One should know the exact meaning of those Notes. 

0

u mean complement of ambiguous grammar and unambiguous grammar meaning different?

this question comes from there

https://gateoverflow.in/181618/decidability

https://gateoverflow.in/19947/which-of-the-folowing-are-r-e?show=166754#c166754



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,157 questions
43,608 answers
123,961 comments
42,860 users