Finding a Regular Grammar

126 Views Asked by At

so I have to find a regular grammar to generate the following sets:

$(1)$ $\{aa, ab, ac\}$
$(2)$ $\{ab^n,ba^n\mid n\ge 0\}$
$(3)$ $\{ab^{2n}\mid n\ge0\}$

I'm wondering if anyone can check my work and let me know if I'm correct. If not, any help/assistance would greatly be appreciated!


$(1)$ $$\begin{align*} &S\to A\\ &A\to aa\\ &A\to ab\\ &A\to ac \end{align*}$$

Is this correct for $(1)$? Do I need $A\to\lambda$?

Edit: Is another alternative/correct/better/worse solution:

$$\begin{align*} &S\to A\\ &A\to aB\\ &B\to a\\ &B\to b\\ &B\to c \end{align*}$$


$(2)$

$$\begin{align*} &S\to AB\\ &S\to BA\\ &A\to aA\mid a\\ &B\to bB\mid b \end{align*}$$


$(3)$

$$\begin{align*} &S\to AB\\ &A\to a\\ &B\to bB\mid b \end{align*}$$

Thanks for your time!

1

There are 1 best solutions below

4
On BEST ANSWER

Your first grammar does generate the language $\{aa,ab,ac\}$, but whether it is regular depends on exactly what definition of regular grammar you have. By this one, for instance, it is not regular, because none of your productions is allowed in either a right regular or a left regular grammar. Your second grammar for that language, however, is regular (specifically, right regular).

Your grammar for $(2)$ is not regular, thanks to the first two productions, and it does not generate the right language. It allows the derivation

$$S\Rightarrow AB\Rightarrow aAB\Rightarrow aaB\Rightarrow aabB\Rightarrow aabb\;,$$

even though $aabb$ is not in the language. Try this instead:

$$\begin{align*} &S\to aB\mid bA\mid a\mid b\\ &A\to aA\mid a\\ &B\to bB\mid b \end{align*}$$

The production $S\to AB$ in your grammar for $(3)$ is again problematic, but you clearly don’t need $A$: you could just as well have $S\to aB$ and do away with the second production. Your non-terminal $B$ doesn’t quite do what you want, however, since it can produce any non-empty string of $b$s; your grammar generates the language $\{ab^n:n\ge 1\}$. You need to make two modifications. First, you have to allow the grammar to generate the word $a$; this is most easily done as I did in my grammar for $(2)$. Secondly, you have to make sure that $B$ generates an even number of $b$s. If you have a more general definition of regular grammar than the one at the link above, you can do this with productions $B\to bbB\mid bb$. If not, you’ll need to introduce another non-terminal, say $X$, and have $B\to bX$ and two $X$ productions; can you figure out what they should be? I’ve left the answer in the spoiler-protected block below.

$X\to bB\mid b$.