Identify the language

Question

Consider the following context sensitive productions.

$$\begin{align}S &\to bSb \mid AcA\\
Ab &\to A\\
Ab &\to b\\
bA &\to b\\
bA &\to A
\end{align}$$

$G$ be a grammar given all the rules except the last, $G'$ be the grammar by all the rules mending the last.

Among $G$ and $G'$ which one is regular, which one is not?

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

I told both regular, which is wrong according to ans. If one is regular ,can another be non regular?

Comments

i dont think G is regular. here is my solution.

S->$b^n$ S $b^n$ (using S->bSb n times)

S->$b^n$ AcA $b^n$ (S->AcA)

S->$b^n$ Ac $b^m$ where m<=n (using Ab->A for some time, then Ab->b)

S->$b^n$ c $b^m$ (using bA->b)

this grammer is not regular because of the condition m<=n. a comparision is required. its a DCFL.

but i am not getting whats G'? whats "mending" the last rule means?

---

Regular Expression G''=( AⁿCB^m  n,m>1 )  Regular...

    G=(AⁿCB^{m )}  n>=m>1  not regular

Answer 1

Case 1.

Grammar without the last production rule.

 

We have the production that can reduce number of b's on the right side of the terminal c. That is b's on the left must be more or equal to the b's on the right. Not regular.

$a^{m}cb^{n} ( m>= n , n > 0 and m > 0)$

 

Case 2.

Grammar with the last production rule included . We now have the power to change the number of b's on either side of c. Hence regular.
$a^{m}cb^{n} ( n > 0 and m > 0)$