Regular languages and constructing a regular grammar

Question

I'm pretty new to computer science and just read about the concept of grammars. Now, I have a practical problem to solve. Here is the alphabet {a, b, c, d}.

How can I determine if the language consisting of all strings a^k b^n c^m d^l, where all k,n,m,l >= 1 is regular. I need to do this because as far as I got all regular languages may be parsed by a regular expression. So, to avoid generating my own parser and lexer, is it possible to do so?

My first attempt was to construct a regular grammar generating the language. I failed, but that doesn't mean that the grammar does not exist. I would appreciate any advice.

Answer 1

First of all it is enough if we can give regular expression for a regular language. To determine if a language is regular you have to show existence of a DFA or a regular expression for the language. Or you can show it is regular if you can prove it is union, intersection, concatenation, etc. (operations under which regular languages are closed) of other known regular languages.

The language in question is regular because it has regular expression $aa^*bb^*cc^*dd^*$.

To construct a regular grammar you need to do it step by step.

$A \rightarrow aA\ \ | \ \ a$
$B \rightarrow bB\ \ | \ \ b$
$C \rightarrow cC\ \ | \ \ c$
$D \rightarrow dD\ \ | \ \ d$

Then finally,

$S \rightarrow ABCD $

Yet another method to get a regular grammar is to convert from DFA. Then you will get (which might be a little difficult to understand right away):

$S \rightarrow aA$
$A \rightarrow aA\ \ |\ \ bB$
$B \rightarrow bB\ \ |\ \ cC$
$C \rightarrow cC\ \ |\ \ dD$
$D \rightarrow dD \ \ |\ \ \epsilon $

My two cent opinion is directly write a lexer (or use automatic-lexer-generator like flex) rather than writing a parser (or using automatic-parser-generator like bison).