+1 vote
222 views

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?

| 222 views
0
L3 is DCFL but L2 is CFL only. i am not sure about DCFL of L2

(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

by Boss (18k points)
selected
0
Thanks.. just one doubt regarding L2 .. how is it finite ? Since |n(a) - n (b) | <= 2 .. why can't we have strings like aaabbbbb .. ?we can have infinite such combinations..

I dint get the significance of "prefix " here .. can you pls explain ?
0

X is a prefix of a string y if there exists xz = y and x is a proper prefix if x is not equal to y.

i.e. for the string aaabbbbb, the prefixes are: $\epsilon$, a, aa, aaa. aaab, aaabb, aaabbb, aaabbbb and aaabbbbb. see this for more on prefix: https://stackoverflow.com/questions/34937067/prefix-of-a-string

Now for the prefix aaa, number of (a) = 3 and number of (b) = 0, This does not satisfy the property given for the language. The property |n(a) - n(b)| <= 2 should be satisfied for all the prefixes. Therefore, that string is not in L2.

0
Great, Thanks :)