Register

DCFL or not

877 views

1 Answer

3 votes
3 votes
See the thing is, there is no non determinism here. Simply because, we have 2 cases.

Case 1: If input starts with a and is followed immediately by b, then you know for sure it's L1.

Case 2: After a, if you see another a, then you know for certain it's L2. So clearly it is a DCFL.

You can simply follow up with their PDAs with these guidelines, and see there's no non determinism. The main key in this question is that 'a' and 'ab' are acting as a clue here. Had it been the case that both the languages started with aa, then it won't be DCFL.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

4 votes
4 votes
2 answers
1
srestha asked Jun 22, 2018
1,611 views
DCFL or Not
$\left \{ a^{m+n}b^{m+n}c^{n}|m,n\geq 1 \right \}$ $\left \{ a^{m+n}b^{m+n}c^{k} |m,n,k\geq 1\right \}$ $\left \{ a^{m+n}b^{m+k}c^{n+k} |m,n,k\geq 1\right \}$ Which one DCFL, CFL or CSL?
$\left \{ a^{m+n}b^{m+n}c^{n}|m,n\geq 1 \right \}$$\left \{ a^{m+n}b^{m+n}c^{k} |m,n,k\geq 1\right \}$$\left \{ a^{m+n}b^{m+k}c^{n+k} |m,n,k\geq 1\right \}$Which one DCFL...
User Avatar
1 votes
1 votes
2 answers
2
atul_21 asked Dec 21, 2017
865 views
DCFL or not??
$L1 = \bigl\{a^mb^nc^pd^q \mid m+q = n+p \bigr\}$ $L2 = \bigl\{a^mb^nc^pd^q \mid m+p = n+q \bigr\}$ 1. L1 is DCFL, L2 is not 2. L2 is DCFL, L1 is not 3. Both are not DCFL 4. Both are DCFL
$L1 = \bigl\{a^mb^nc^pd^q \mid m+q = n+p \bigr\}$$L2 = \bigl\{a^mb^nc^pd^q \mid m+p = n+q \bigr\}$1. L1 is DCFL, L2 is not2. L2 is DCFL, L1 is not3. Both are not DCFL...
User Avatar
1 votes
1 votes
1 answer
4
Himanshu1 asked Nov 2, 2015
1,008 views
Unambiguous CFL which is not DCFL
Give an example of Unambiguous CFL which is not DCFL .
Give an example of Unambiguous CFL which is not DCFL .
User Avatar
Link Copied!