The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

1)Let G be CFG. Whether L(G) is CFL.

Q)Is it decidable or not?

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

Q)Is it decidable or not?

Q)Is it decidable or not?

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

Q)Is it decidable or not?

+2 votes

Best answer

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)

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

+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

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

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?

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

0

"Given G is some CFG and whether L(G) will be DCFL or Not" ...that would be Undecidable. Please justify [email protected] Deepakk Poonia (Dee)

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 450
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,106 questions

45,608 answers

132,246 comments

49,231 users