701 views
1 votes
1 votes

Consider the statements

(I) Regular
(II) DCFL but not regular
(III) CFL but not DCFL

Now consider the three languages L1, L2,L3 given below , and choose the correct option.

(L1) {aibjck|i=k or j=k}

(L2) {aibj|for every prefix of the string |n(a)-n(b)|≤2 
where n(a)=number of a & n(b)=number of b}

(L3) {aibj|if n(a)=number of a & n(b)=number of b 
then, |n(a)-n(b)|≤2 for all strings}

what will be the correct matching ?

i know L1 is CFL but not DCFL , what about L2 and L3?

1 Answer

Best answer
3 votes
3 votes

(L1) $\{ a^i b^j c^k | i = k or j = k \} $

This is CFL but not DCFL. Because we don't know whether we have to match the number of $a$'s and number of $c$'s (i.e i = k), or the number of $b$'s and number of $c$'s (i.e j = k). So, a non-deterministic choice has to be taken.

(L2) $\{ a^i b^j |\ for\ every\ prefix\ of\ the\ string\ | n(a) - n(b) | \leq 2,\ where\ n(a) = number\ of\ a\ and\ n(b) = number\ of\ b \} $

This language is regular. In fact, this language is finite. It contains the strings: $\{ \epsilon , a, ab, abb, abbb, b, bb, aa, aab, aabb, aabbb, aabbbb \} $. You can check that there are no more strings in it.

(L3) $\{ a^i b^j |\ if\ n(a)=number\ of\ a\ and\ n(b)=number\ of\ b\ then,\ | n(a) - n(b) | \leq 2\ for\ all\ strings \} $

It is DCFL, but not regular. The deterministic pushdown automate can be built as follows: For every $a$, push into the stack, then for a $b$ move to another state where we pop for every $b$, When input completes or stack is empty, move to another state and compare the number of $b$'s left, or extra $b$'s in the remaining input. 

(L3) is not regular since it requires a comparison between the two quantities, and the finite memory cannot do it.

Final matching is:

(L1) - (III) CFL but not DCFL

(L2) - (I) Regular 

(L3) - (II) DCFL but not regular 

selected by

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
2
practicalmetal asked Mar 15, 2023
496 views
Is the following language context free:The set of all strings with number of a’s equal to number of b’s and the sum of a’s and b’s to be divisible by 3.