The Gateway to Computer Science Excellence
+1 vote

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?

in Theory of Computation by Active (2.2k points) | 222 views
L3 is DCFL but L2 is CFL only. i am not sure about DCFL of L2

1 Answer

+2 votes
Best answer

(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 by
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 ?

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:

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.

Great, Thanks :)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,748 answers
108,121 users