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) {a^{i}b^{j}c^{k}|i=k or j=k}

(L2) {a^{i}b^{j}|for every prefix of the string |n(a)-n(b)|≤2

where n(a)=number of a & n(b)=number of b}

(L3) {a^{i}b^{j}|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?

+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 **

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 ?

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,748 answers

199,477 comments

108,121 users