3
|
10055 Views
|
4 Replies
|
11 Total Likes
View groups...
Share
GROUPS:

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

Posted 11 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.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 Replies
Sort By:
Posted 11 years ago
 The regular grammar will be:G = ({1,a,b},{S,A,B,C,D}, P, S) , where P:S -> 1AA -> aB|aCB -> 1B|aB|bB|aCC -> a|aDD -> 1|a|b|1D|aD|bD
Posted 11 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.
Posted 11 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)rules={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 listrules2 = {x___, #[[1]], y___} -> Flatten[{x, #[[2]], y}] & /@ ruleskeeping 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 rulesNestList[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.Union[ Select[Flatten[   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 11 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} | Nulldoubleasubchain = {anychain,aa,anychain}