1
$\begingroup$

I know that a regular grammar has a definition

$$\begin{align}S &\to aS\\ S &\to \lambda \end{align}$$

But I dont really know how to apply this information to check whether or not a grammar is regular...

So for example I have a grammar $$\begin{align}S &\to aSbSb\\ S &\to \lambda \end{align}$$

If I compare it to the definition of a regular grammar this is not a regular grammar right? Which also means that I can't turn this into a regex.

Also could you please give me an example of a regular grammar and a non-regular grammar hopefully that will solidify my understanding.

$\endgroup$
  • $\begingroup$ You're using lambda to mean the empty string, I'm guessing? $\endgroup$ – Draconis Aug 15 at 2:24
  • $\begingroup$ @Draconis yes lambda is empty strkng $\endgroup$ – alexW Aug 15 at 6:31
  • $\begingroup$ @Draconis Yes. But it hardly matters: worst-case is that you think that $\lambda$ is just some character in the alphabet and the first grammar describes the language $\{a^n\lambda\mid n\geq 0\}$, and that's essentially identical to the intended language. $\endgroup$ – David Richerby Aug 15 at 7:47
6
$\begingroup$

It's important to distinguish between regular grammars and regular languages.

Your first grammar is regular.

A regular grammar is either a right-regular grammar or a left-regular grammar. In a right-regular grammar, every production's right-hand side has at most one non-terminal, and that non-terminal is the last symbol in the right-hand side. A left-regular grammar is the same except that all the non-terminals are at the beginning of their respective right-hand sides.

As you observe, your second grammar is not a regular grammar, since there is a right-hand side with more than one non-terminal.

A regular language is a language for which a regular grammar exists. That's a much trickier criterion, since the fact that a particular grammar is not regular does not in any way prove anything about the regularity of the language generated by that grammar. The language might or might not be regular, and there is no algorithm which will even tell you for sure.

So your statement "Which also means that I can't turn this into a regex." does not follow. As it happens, your second grammar does not generate a regular language, but many non-regular grammars do recognise regular languages. Here's a simple example:

$$\begin{align}S &\to aS\\ S &\to Sb\\ S &\to \lambda \end{align}$$

That grammar generates the language $a^*b^*$, which is certainly a regular language. But this particular grammar is not regular because one production is left recursive and the other production is right recursive; in a regular grammar, either all productions with a non-terminal are left-regular, or all productions with a non-terminal are right-regular.

$\endgroup$
  • $\begingroup$ Should the last sentence say "in a regular grammar" instead of "in a regular language"? $\endgroup$ – Curtis F Aug 15 at 14:35
  • $\begingroup$ @curtis: yes, indeed. Fixed, thanks. $\endgroup$ – rici Aug 15 at 15:01
  • $\begingroup$ Okay that cleared up my misunderstanding about regular languages and regular grammar. So is it true that if a grammar produces a regular language there is a regex conversion? $\endgroup$ – alexW Aug 16 at 5:55
  • $\begingroup$ @alexw: If a grammar produces a regular language, there is a regular expression which produces the same language. However, there is no algorithm which will tell you what that regular expression is (unless the grammar is regular). $\endgroup$ – rici Aug 16 at 13:32
1
$\begingroup$

You are correct that the grammar $S \rightarrow aS \mid \lambda$ is regular. However, there are a lot of regular languages out there (a countably infinite number in fact!), so even if your grammar doesn't look like this, it can still be a regular language.

The standard way to show that a language is regular is to write a regular expression for it (or build a NFA, etc). And the standard way to show that a language is not regular is to use the Pumping Lemma.

But, the Pumping Lemma doesn't always work. And is kind of a pain in the ass to use. So instead, this is the Distinguishable Prefix Lemma, an alternate way to show non-regularity:

Let $X$ be a set of strings. If, for any two distinct strings $x_1$ and $x_2$ in $X$, you can come up with some string $y$ such that $x_1y$ is in your language and $x_2y$ is not, then $X$ is called a distinguishable prefix set.

If you can find an infinite distinguishable prefix set, then your language is not regular.

Write out some example strings in the language, and try to solve this yourself, using this lemma, before reading further!


You may have noticed that the string $a^i b^j$ is in the language, if and only if $j=2i$. (This doesn't cover the entire language, but that doesn't matter for this proof.)

So let's make $X$ be $a^i$ (for all natural $i$). Now, take two arbitrary distinct members from this set; let's say that $x_1 = a^n$ and $x_2 = a^m$, for arbitrary $n \neq m$.

Set $y = b^{2n}$. Now $x_1y = a^nb^{2n}$ is in the language, and $x_2y = a^mb^{2n}$ is not. And there are infinite natural numbers.

Therefore $X$ is a distinguishable prefix set, and has infinite members. So your language is not regular.

P.S. What I call the "Distinguishable Prefix Lemma" is a special case of the Myhill-Nerode Theorem, which is stronger than the Pumping Lemma! I'm not sure Myhill and Nerode used this name for the lemma, but it's what I learned, so I'm sticking to it.

Myhill-Nerode can actually show that a language is regular, too, but it's usually way more difficult in that direction. So you'll probably only want to use this method to show that something is not regular, not that it is.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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