ME Demo Test Q13

Question

Consider the following statement:

S : {$a^{n}b^{n+k} | n\geq 0,k\geq 1$} $\cup$ {$a^{n+k}b^{n} | n\geq 0,k\geq 3$}

Which of the following is TRUE about S? (Also explain HOW)

• A. S is Regular, but not DCFL
• B. S is CFL, but not DCFL
• C. S is DCFL, but not Regular
• D. None of these

Comments

@Pranavpurkar @Kabir5454

Correct. Can you tell how?

DCFL not closed in Union. Then how?

If we try to merge I think we'll get $a^{n}b^{m}, where, n \neq m$

If I'm wrong pls correct

---

Never check the closure property if the particular language is given . Apply closure property if the question about are CFL closed under complement ? Then you can apply closure property. Because the closure property may satisfy for some language say L= { a^nb^n | n>0} , where Sigma={a,b} .

Now complement of L is also CFL but as per closure property CFL are not closed but here it is closed. So if particular language is given check only that language as it is maintaining the given property or not.

Come to this language:-

1)First push all the "a's" .

2) pop "a's" till you see B's .

3) Then there is 2 case

    3.1) say stack Has gone empty now you        see only have B's left in the string. So that should be your final state as it will accept all the string of {a^nb^n+k| k>0}

3.2) another case is b got empty but stack still has a's left. So we have to check atleast 3 a's are left in the stack or not. So if it does it will be accepted state or not.

---

@Kabir5454

I got it. Thank you 🙏😊

Answer 1

@Jaideepyadav910

When languages are given don’t go by the general property , check for the given languages.

$S$ : {$a^nb^{n+k}|n≥0,k≥1$} $∪$ {$a^{n+k}b^n|n≥0,k≥3$}

here , considering the first language

$L1$ $=$  {$a^nb^{n}b^{k}|n≥0,k≥1$}

Here there is only one dependency and k is independent  of n , it can be written as $a^nb^nb^+$ , clearly $DCFL$.

similarly the other language is also $DCFL$.

Union contains all the Strings from both the set of languages.

-------------------------------------------------------------------------------------------------------------------------------------------------

DCFL not closed in Union. Then how?

NOT CLOSED means it may or may not be DCFL.

Comments

@Pranavpurkar

I got it. Thank you 😊🙏

push and pop are clear in both, so it's DCFL.