# How to build a regular grammar for a regular language?

GROUPS:
 Alex D 3 Votes How to build a regular grammar for a formal regular language?The language is an infinite set of chains that are defined by the next conditions.Conditions:1) The language chains only consist of symbols from the set {1,a,b}.2) The language chains always start from a subchain '1a'.3) Every languange chain has to include at least one subchain 'aa'.For example:1aa, 1aaa, 1abaa, 1aaba, 1aaab, 1aab1a, ... etc.The regular expression in formal language seems to be like this: 1a ((1+b)* a)* (a (1+b)) a (1+b+a)*What will the correct regular grammar be for this language?I wrote a grammar that generates the chains that start from '1a'. But still I don't know how to make it include at least an 'aa' subchain.G ({1,a,b}, {A,S}, P, S), where P is:S -> 1aAA -> 1A | aA | bA | a | b | 1
4 years ago
4 Replies
 Daniel Lichtblau 2 Votes I think you ant something like this. I use | for "alternatives} and curly braces for a sequence.chain = {1,a,a,anychain}  |  {1,a,doubleasubchain}anychain = {1|a|b,anychain} | Nulldoubleasubchain = {anychain,aa,anychain}