5
$\begingroup$

To be concrete, consider the following formal grammar: $$S \rightarrow aSb$$ $$S \rightarrow \varepsilon$$

The language generated by this grammar is $L = \{ a^n b^n | n \geq 0 \}$. How can I implement this grammar and ask Mathematica to compute its corresponding language? Thanks!

EDIT: I don't want to implement this grammar from scratch, using basic functionalities in Mathematica. I'm looking for Mathematica functions designed to deal with this problem.

$\endgroup$
7
  • $\begingroup$ And what kind of mathematical apparatus is used to formally describe grammar? $\endgroup$
    – dtn
    Dec 31, 2022 at 13:37
  • 1
    $\begingroup$ @dtn Set theory as far as I know. $\endgroup$
    – Integral
    Dec 31, 2022 at 13:50
  • $\begingroup$ Maybe I wasn't specific enough but I don't want to implement this grammar from scratch, using basic functionalities in Mathematica. I'm looking for Mathematica functions designed to deal with this problem. $\endgroup$
    – Integral
    Dec 31, 2022 at 13:58
  • $\begingroup$ reference.wolfram.com/language/guide/… check out this link for some ideas and inspiration. It is possible that experts in language research will suggest more. To solve highly specialized problems, packages can be developed that can be integrated into Mathematica.In the future, you should look for them, for example, on GitHub. $\endgroup$
    – dtn
    Dec 31, 2022 at 14:03
  • 3
    $\begingroup$ You can generate random examples from your grammar very easily: Table[ FixedPoint[StringReplace[#, RandomChoice@rules] & , "S"], {50}] // DeleteDuplicates If you want to jump straight to the general form $a^n b^n$ then that is kind of hard. I recommend using a program called JFLAP for this which will allow you to generate regexes / pushdown automata for DFA's/NFA's / context free grammars. Here's the PDA for your one imgur.com/a/xBC5FPl . $\endgroup$
    – flinty
    Dec 31, 2022 at 14:30

1 Answer 1

8
$\begingroup$

Just for fun, a basic attempt at a function, with three languages used as examples:

Note that n is just the number of times through the loop. We could instead loop until we collect n words, but then we have to be sure that the rules do generate these words.

generateLanguage[start_String, terminal_List, variable_List, 
  rules_List, n_Integer] := Module[{language, running, i},
  language = {};
  running = {start};
  i = 1;
  While[i <= n,
   running = 
    Flatten@(StringReplaceList[#, rules] & /@ Flatten@running);
   If[StringCount[#, variable] == 0, AppendTo[language, #]] & /@ 
    running;
   i++;
   ];
 DeleteDuplicates@language
  ]

EXAMPLE 1: $L = \{ a^n b^n | n \geq 0 \}$

rules = {"S" :> "aSb", "S" :> ""};
startSymbol = "S";
terminal = {"a", "b"};
variable = {"S"};
generateLanguage[startSymbol, terminal, variable, rules, 14]

(* {,ab,aabb,aaabbb,aaaabbbb,aaaaabbbbb,aaaaaabbbbbb,aaaaaaabbbbbbb,aaaaaaaabbbbbbbb,aaaaaaaaabbbbbbbbb,aaaaaaaaaabbbbbbbbbb,aaaaaaaaaaabbbbbbbbbbb,aaaaaaaaaaaabbbbbbbbbbbb,aaaaaaaaaaaaabbbbbbbbbbbbb} *)

EXAMPLE 2: $L = \{ (a b)^n | n \geq 1 \}$

rules = {"S" :> "Tb", "T" :> "a", "T" :> "Sa"};
startSymbol = "S";
terminal = {"a", "b"};
variable = {"S", "T"};
generateLanguage[startSymbol, terminal, variable, rules, 15]

(* {ab,abab,ababab,abababab,ababababab,abababababab,ababababababab} *) 

EXAMPLE 3: $L = \{ a^n b^n c^n | n \geq 1 \}$

(Slow! Keep n low)

rules = {"S" :> "aSTU", "S" :> "aTU", "UT" :> "TU", "aT" :> "ab", 
   "bT" :> "bb", "bU" :> "bc", "cU" :> "cc"};
startSymbol = "S";
terminal = {"a", "b", "c"};
variable = {"R", "S", "T", "U"};
generateLanguage[startSymbol, terminal, variable, rules, 12]

(* {abc,aabbcc,aaabbbccc} *)

enter image description here enter image description here

$\endgroup$
2
  • $\begingroup$ How did you generate these images? $\endgroup$
    – Integral
    Jan 8, 2023 at 14:09
  • $\begingroup$ I made these images a few years ago for some common, specific languages, using the function Graph[] and manually entering the details. I added these here so people unfamiliar with the process could see how these transformations generate specific words of the language. $\endgroup$ Jan 8, 2023 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.