11
$\begingroup$

I am new to automata, and I have been given a brief introduction to regular expressions only yesterday. I have read the various rules which to define a regular expression. But I am unable to differentiate between regular expressions and grammar of a language( I have not been taught the grammar for regular expressions).

I understand that grammar helps us to generate the valid strings in a language, but then this is what the rules for defining a regular expressions state. So where does the difference lie? I asked my professor and he said that regex are the most basic strings in a language and grammar is the set of rules for any language, which are of higher order than regex. Can someone provide some more in-depth information?

$\endgroup$
21
$\begingroup$

Regular expressions, regular grammars and finite automata are simply three different formalisms for the same thing. There are algorithms to convert from any of them to any other.

The basic reason that we have all three is that they were created independently, with the first set of equivalences (there are several other formalisms as well) proven by Kleene (this result, or part thereof is called Kleene's Theorem).

So in that context, depending on which way round you want to run the models, they all recognise or generate strings of a regular language, and mathematically, there is, in that sense, no difference.

Of course sometimes one model is easier to use than another for a particular task, due to the details of the formalism. Furthermore the way they work in a human's head is often a little different, finite automata "feel" like computers, regular expressions "feel" like you're constructing a string out of smaller substrings and regular grammars "feel" like a more traditional grammatical derivation or classification of a sentence in a language (unsurprisingly when you look at the history).

So to compare the two, let's define them:

Regular Expressions

So regular expressions are recursively defined as follows:

  1. $\emptyset$ is a regular expression
  2. $\varepsilon$ is a regular expression
  3. $a$ is a regular expression for every $a \in \Sigma$
  4. if $A$ and $B$ are regular expressions then
    • $A\cdot B$ is a regular expression (concatentation)
    • $A \mid B$ is a regular expression (alternation)
    • $A^{\ast}$ is a regular expression (Kleene star)

Along with some semantics (i.e. how we interpret the operators to get a string), we get a way of generating strings from a regular language.

Regular Grammars

Regular grammars consist of a four tuple $(N,\Sigma, P, S \in N)$ where $N$ is the set of non-terminals, $\Sigma$ is the set of terminals, $S$ is the start non-terminal and $P$ is the set of productions which tell us how to change the start symbol, step by step, into a string in $\Sigma^{\ast}$. $P$ can have its productions drawn from one of two types (not both though):

Right Linear Grammars

For non-terminals $B$, $C$, terminal $a$ and the empty string $\varepsilon$, all rules are of the form:

  1. $B \rightarrow a$
  2. $B \rightarrow aC$
  3. $B \rightarrow \varepsilon$

Left Linear Grammars

Left linear grammars are the same, but rule #2 is $B \rightarrow Ca$.

Things to Ponder

So looking at these definitions and playing with them, we can see that regular expressions look like matching rules, or ways of dealing with strings a bit at a time.

Grammars seem to "label" sections of the string, and group labels under new labels to validate the string (i.e. if we can get from $S$ to the string, or vice versa, we're happy).

However these are really doing the same fundamental thing, and how you view the metaphor of their function is really up to you.

$\endgroup$
  • $\begingroup$ I'd put more emphasis on the fact that grammars generate strings in the language, while regular expressions (as you said) are more of a matching pattern that matches (or, "test") every string in the language. $\endgroup$ – Ran G. Sep 1 '15 at 5:38
  • $\begingroup$ @RanG., that is indeed the usual way to think of it, but you can flip both around; bottom up parsing tests a string against a grammar, and you can use a regular expression as a compact description of a language (though this is probably less common). $\endgroup$ – Luke Mathieson Sep 1 '15 at 6:08
  • $\begingroup$ @simpleBob $N$ is the set of nonterminals, $S$ is the starting nonterminal. What would $R$ be? $\endgroup$ – Luke Mathieson Nov 30 '15 at 23:06
  • $\begingroup$ @LukeMathieson My mistake, I read the paragraph and thought it was a typo with $N$ because of the order where $R$ was defined. Now that I have read the formal definition elsewhere, it seems that the typo was that $R$ should be $P$ (I think) (Second line in the first Regular Grammars paragraph) $\endgroup$ – Daniel Dec 1 '15 at 18:27
  • $\begingroup$ @simpleBob, Ah yes, that's definitely a typo. Thanks! $\endgroup$ – Luke Mathieson Dec 1 '15 at 23:34

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.