I'm currently doing some self study to improve my half-forgotten college theory of comp skills.
I'm going over some problems from an old book and it asks you to find a regular grammar for the pictured NFA. The language of the NFA is a+b+ , but I do not know the steps in finding the regular grammar. I understand regular grammar when presented to me, but find it hard to place together all the possible scenarios without forgetting some.
For example, I started and came up with:
S -> aAb | aBb | ab
A -> aA | a
B -> bB | b
I know its not correct but i'm stuck on how to start building the grammar from scratch. Can anyone help define some steps to take to solve the problem?
Your grammar should simply produce a string of one or more $a$’s followed by a string of one or more $b$’s. One set of productions that will do this is:
$$\begin{align*} &S\to aS\mid aB\\ &B\to bB\mid b \end{align*}$$
Here $S$ is the initial symbol. We can begin by applying the production $S\to aS$ any non-negative number of times, but eventually we must apply $S\to aB$ if we’re to generate a terminal string. If we applied $S\to aA$ $n$ times, at that point we have $a^{n+1}B$. We can then apply $B\to bB$ any non-negative number of times, but eventually we must apply $B\to b$ to complete the derivation of a terminal string. If we applied $B\to bB$ $m$ times, we end up with $a^{n+1}b^{m+1}$. Since $n$ and $m$ are any non-negative integers, we can generate all words of the form $a^kb^\ell$ with $k,\ell\ge 1$, and those are precisely the words described by the regular expression $a^+b^+$.