Consider the following subsets of $\{ a, b, \$ \} ^*$: $A = \{ xy \mid x,y \in \{ a, b, \} ^*, \#a(x) = \#b(y) \}$ and $B = \{ x \$ y \mid x,y \in \{ a, b, \} ^*, \#a(x) = \#b(y) \}$. Which of the following statements are true?
- $A$ and $B$ both are regular.
- $A$ is regular but $B$ is not.
- $A$ is not regular but $B$ is.
- Both are non-regular.
According to me both should be non-regular since for the first one regular expression would be $(a+b)*$ but we can't make a FA for it representing equal no of $a$'s and equal no of $b$'s. Also similar argument for second language.
Your first langauge is :
$$A = \{xy | x,y \in \{a,b\}^*,\#a(x)=\#b(y) \}$$ Which means number of a's in x is equivalent to number of b's in y; where $x\in\{a,b\}^*$ and $y\in\{a,b\}^*$.
Therefore,
$xy = \{a,b\}^*\{a,b\}^*= \{a,b\}^*$
$A = \{w\mid \#_a(w)=\#_b(w)\}$ is not regular.
CFG for $A$
$$S → aSbS | bSaS |\in $$
Your second langauge is :
$$B = \{x\$y | x,y\in \{a,b\}^*,\#a(x)=\#b(y)\}$$ Which means number of a's in x is equivalent to number of b's in y; where $x\in\{a,b\}^*$ and $y\in\{a,b\}^*$.
$$B = x$y = \{\{a,b\}^*$\{a,b\}^*| x,y\in \{a,b\}^*,\#a(x)=\#b(y)\}$$ Which is not regular, since we can't matching in DFA. We need stack for both langauges.