Register

Decidability

• retagged by
2,813 views

1 Answer

Best answer
9 9 votes

Given a language DCFL it is always unambiguous because as we have no non determinism and we can define the moves of PDA deterministically..

In other terms there exists at least a one DCFG for a given DCFL which is unambiguous ..Hence ambiguity problem for a DCFL is a trivial property as we are able to say 

Given a DCFL it is always unambiguous ..

Hence the ambiguity problem of DCFL is decidable..

As far as CFL is concerned it may be ambiguous or unambiguous..Actually there is a term "inherent ambiguity" which begins from CFL layer..So given a CFL it may be ambiguous or unambiguous..And we have no such definite algorithm which can decide ambiguity of a given CFL..

Hence the ambiguity problem of CFL is undecidable..

• selected by
Voting & Accepting an answer helps improve the community
← Previous · compilers(ullman)Next → · Type of error
← Previous in category · Decidablity+DCFLNext in category → · Are CSL, RE, Recursi...
Position:
Show:

Related questions

0 0 votes
1 1 answer
2.0k
2.0k views
Hardik Maheshwari asked Jan 14, 2019
2,012 views
Test Series
If $L_1$ is DCFL and $L_2$ is context free language. Consider the below given statementsWhich is correct between these and why ? (S1 is correct.. but why ??) . I couldn’...
0 0 votes
1 answers 1 answer
794
794 views
Shubham Kumar Gupta asked Dec 24, 2017
794 views
Deterministic Context Free Languages
Qus: If L1=DCFL, L2= DCFL then L1-L2=?Sol: We can see from the above figure that DCFL’s are not closed under difference operation so L1-L2 = L3, is not a DCFL.The doubt i...
2 2 votes
2 2 answers
3.9k
3.9k views
rahul sharma 5 asked Nov 21, 2017
3,913 views
[TOC] Basic doubt in DPDA
Following is the PDA that accept equal number of a and b.How can this be converted to DPDA? When stack top is Z,that it can read epsillon or a or b,which can create choic...
1 1 vote
1 1 answer
2.9k
2.9k views
rahul sharma 5 asked Jul 31, 2017
2,851 views
TOC DPDA vs NPDA
How many stacks are available with DPDA and NPDA? I assume it is 1 with DPDA and n with NPDA where n is some constant.Assume i have a language ,over alphabet a,b,c,dL=( W...