0
$\begingroup$

I'm really stuck here and do not know what to do. So far, I've constructed a DFA and a regular expression that produces the aforementioned set of strings. Namely, the DFA looks like: enter image description here

After a lot of efforts I managed to find a concise regular expression of it, namely: $$ b^*\left( a + (b \; | \; bbb+)\right)^*a^*b^*.$$

What I have tried so far as to construct the desired regular grammar is: \begin{align*} q_0 &\rightarrow b \ | \ a \ | \ aq_1 | \ ε \ \\ q_1 &\rightarrow aq_1 \ | \ bq_2 \ | \ ε \ \\ q_2 &\rightarrow aq_0 \ | \ bq_3 \ | \ ε \ \\ q_3 &\rightarrow bq_0 \ | \ aq_4 \ | \ ε \end{align*}

Obviously $q_4$ is non-yielding, therefore we can omit it, and we get

\begin{align*} q_0 &\rightarrow b \ | \ a \ | \ aq_1 | \ ε \ \\ q_1 &\rightarrow aq_1 \ | \ bq_2 \ | \ ε \ \\ q_2 &\rightarrow aq_0 \ | \ bq_3 \ | \ ε \ \\ q_3 &\rightarrow bq_0 \ | \ ε \end{align*}

Correct me if I'm wrong but the above rules as is, define a context free grammar since we have more than one non-Terminal symbol on the right side. How can I turn the above rules into a regular grammar? Any help would be greatly appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

That already is a regular grammar; in particular, it is right-regular.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.