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.

  • 3
    $\begingroup$ Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$
    – Raphael
    Feb 17 '16 at 11:22
  • $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – Raphael
    Feb 17 '16 at 11:22

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).


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.