Message Boards Message Boards

How to build a regular grammar for a regular language?

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.
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 -> 1aA
A -> 1A | aA | bA | a | b | 1
4 years ago
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} | Null
doubleasubchain = {anychain,aa,anychain}
POSTED BY: Daniel Lichtblau
4 years ago
Still it's unclear to me how to convert this into rules of formal regular grammar.
I can easily convert my regexp into a context-free grammar using 5 rules {S,A,B,C,D}, but playing with regular grammar is "slightly" trickier. 
4 years ago
There are general ways of doing these sorts of things but this is a little simpler if you look at it the right way.  For instance this is the union of the language 1a(any)aa(any) with the possible exceptions 1aa(any).

Then just combine the production rules.  e.g. here the role of B is duplicated as the final (any)
{S -> {1, a, A},
S-> {1, a, a, B}, 
A-> {1, A},
A -> {a, A},
 A -> {b, A},
A -> {a, a, B},
B -> {},
B -> {1, B},
B -> {a, B},
B -> {b, B}};

Then production of the words could be implemented with ReplaceList, e.g.,

first setting up the rules to replace a whole list

rules2 = {x___, #[[1]], y___} -> Flatten[{x, #[[2]], y}] & /@ rules

keeping the prefix with x and suffix with y,

{{x___, S, y___} -> {x, 1, a, a, B, y}, {x___, S,
   y___} -> {x, 1, a, A, y}, {x___, A, y___} -> {x, 1, A, y}, {x___,
   A, y___} -> {x, a, A, y}, {x___, A, y___} -> {x, b, A, y}, {x___,
   A, y___} -> {x, a, a, B, y}, {x___, B, y___} -> {x, y}, {x___, B,
   y___} -> {x, 1, B, y}, {x___, B, y___} -> {x, a, B, y}, {x___, B,
   y___} -> {x, b, B, y}}

Then ReplaceList will do all possible production rules

NestList[Flatten[ReplaceList[#, rules2] & /@ #, 1] &, {{S}}, 2]

Here are the first two iterations

{{{S}}, {{1, a, a, B}, {1, a, A}}, {{1, a, a}, {1, a, a, 1,
   B}, {1, a, a, a, B}, {1, a, a, b, B}, {1, a, 1, A}, {1, a, a,
   A}, {1, a, b, A}, {1, a, a, a, B}}}

To get the words in the language select those without S, A, or B.

   NestList[Flatten[ReplaceList[#, rules2] & /@ #, 1] &, {{S}}, 4],
   1], Count[#, S | A | B] == 0 &]]

which yields these after 4 iterations.

{{1, a, a}, {1, a, a, 1}, {1, a, a, a}, {1, a, a, b}, {1, a,
  1, a, a}, {1, a, a, 1, 1}, {1, a, a, 1, a}, {1, a, a, 1, b}, {1, a,
  a, a, 1}, {1, a, a, a, a}, {1, a, a, a, b}, {1, a, a, b, 1}, {1, a,
  a, b, a}, {1, a, a, b, b}, {1, a, b, a, a}}
POSTED BY: Todd Rowland
4 years ago
The regular grammar will be:
G = ({1,a,b},{S,A,B,C,D}, P, S) , where P:
S -> 1A
A -> aB|aC
B -> 1B|aB|bB|aC
C -> a|aD
D -> 1|a|b|1D|aD|bD
4 years ago

Group Abstract Group Abstract