TOC | Made Easy Test Series | Q.13

Question

Consider the following statement

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

The above statement is:

1. TRUE
2. FALSE

 

Answer 1

When languages are given don’t go by the Closure 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$.

Here, in $L1$ push all a’s then pop all b’s for each a and push remaining b’s, thus a PDA can be constructed for this.

similarly the other language is also $DCFL$.

in $L2$ , after pushing all a’s and popping all b’s just check that 3 a’s are present or not,  if present then accept.

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 Do you mean something like this?

---

@Souvik33

Yes.