Message Boards Message Boards

4 Replies
11 Total Likes
View groups...
Share this post:

How to build a regular grammar for a regular language?

Posted 10 years ago
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 Replies
Posted 10 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
Posted 10 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. 
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
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
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract