VirtualGate Test Series: Theory Of Computation - Regular Languages

Question

Consider the following subsets of $\left\{a, b, \$ \right\}^*$

• $A=\left\{xy\, |\, x,y\in\left\{a,b\right\}^*,\#a(x)=\#b(y)\right\},$
• $B=\left\{x\$y\, |\, x,y\in\left\{a,b\right\}^*,\#a(x)=\#b(y)\right\}$

Which of the following statements are true?

1.  $A$ and $B$ both are regular
2. $A$ is regular but $B$ is not
3. $A$ is not regular but $B$ is regular
4. Both are non-regular

Comments

no u can't since $ here is one of the symbol like a and b...

Answer 1

$A=\left\{xy \mid x,y \in\left\{a,b\right\}^*, \#a(x)=\#b(y)\right\}$ is regular and is $(a+b)^*$
As any string can be break in to $x$ and $y$ where no of $a's$ in $x$ = no of $b's$ in $y$, here we are flexible in choosing length of $x$ and $y$ as per our choice. 

example 1: $xy=$$aaaaa$, $x=\epsilon$ ,$y= aaaaa$

example 2:$xy=$$bbbabbbbaa$, $x = bbbabbb$, $y=baa$

And try any other string. remember we are flexible with length of $x$ and $y$.

$B=\left\{x\$y \mid x,y \in\left\{a,b\right\}^*, \#a(x)=\#b(y)\right\}$ is non-regular.

As we need to push $a's$ of $x$ into stack and need to pop them with $b's$ of $y$.

whatever is there before $\$$ is $x$ and after $\$$ is $y$ . we can't choose them. 

Comments

Regularity of A seemed counterintuitive to me, so I tried prove a similar lemma. 

---

n+1 length string can be

xay = (new x)(new y) where new x = old a , new y = a (old y)

or

xby = (new x)(new y) where new x = (old x )b , new y = old y

---

Thanks a lot sir, that would be a better approach than appending new 'a' or 'b' at the end of 'xy'.

---

sir  $A=\left\{xy \mid x,y \in\left\{a,b\right\}^+, \#a(x)=\#b(y)\right\}$
then it will not be regular right?

---

I think that too result in regular language for the same reason as here in A

---

Awesome man !

Answer 2

Answer : B

$A = \left \{ xy | x,y \in \left \{ a,b \right \}^*, n_a(x) = n_b(y) \right \}$

It is Regular. Moreover, $A = \Sigma^*$

Let's Prove it Formally.  

Proof :

We can see easily(check manually) that $\in, a,b,aa,ab,ba,bb$ etc are in the language $A$ (i.e. We can split all these Strings in Two parts such that in the left part there are as many $a's$ as there are $b's$ in right part. Just check manually)

Two length strings can be partitioned as follows : $\left \{ |aa, a|b,b|a,bb| \right \}$

Now, All the Three length strings can be formed by appending $a$ or $b$ to the Two length strings and We already have some partition of Two length strings. So, Here goes the Idea :

"If we append $a$ at the end of any Two length string then the Previous Partition of the Two length string will remain as it is"

i.e. $\left \{ |aaa, a|ba,b|aa,bb|a \right \}$   

"If we append $b$ at the end of any Two length string then the Previous Partition of the Two length string will shift to right by One Position"

i.e. $\left \{ a|ab, ab|b,ba|b,bbb| \right \}$

So, We can inductively say that ""If we append $a$ at the end of any $n-1$ length string then the Previous Partition of the $n-1$ length string will remain as it is" and "If we append $b$ at the end of any $n-1$ length string then the Previous Partition of the $n-1$ length string will shift to right by One position"

Hence, We can say that Every string can be Partitioned in Two parts such that  in the left part there are as many $a's$ as there are $b's$ in right part. So, $A = \Sigma^*$

---

$B$ is Simple and Standard Non-regular CFL.

Answer 3

Answer Should be D.

Both A and B would require a stack for comparing number of a's and b's,therefore they come under CFL language.

Answer 4

A = {xy | x, y ∈ {a, b}*, #a(x) = #b(y)},
this Language is always regular. Actually it will accept every string from (a+b)*.

B = {x$y | x, y ∈ {a, b}*, #a(x) = #b(y)}
This one is NON REGULAR. we cant find middle element from DFA.
 

Comments

"#a(x) = #b(y)"? This will require memory to store the number of x's in a and number of y's in b?