snippetMinor
How do i tell if a grammar is regular or not?
Viewed 0 times
regulartellgrammarhownot
Problem
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.
$$\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.
Solution
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.
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.
Context
StackExchange Computer Science Q#112758, answer score: 9
Revisions (0)
No revisions yet.