Langage équilibré, 2 symboles non-terminaux, compréhension de la liste

Question

Donc, je lisais un livre, "Introduction à la théorie du langage formel" et il décrit une langue L(G) = {a^n ++ b^n | n > 0}.

Il a les productions suivantes:

S -> ab | aSb 

Et produirait la langue suivante:

a, ab, aabb, aaabbb, ... 

Je me demandais comment je pouvais utiliser la compréhension de la liste de Haskell pour créer cette langue. Je sais que je peux faire la compréhension de la liste avec des cordes, mais je suis plutôt débutant et je ne savais pas comment je pourrais obtenir une liste infinie comme je le voudrais de ces cordes.

J'imagine quelque chose comme:

[ x ++ y | x <- ["a","aa",..] y <- ["b","bb",..]] 

Answer 1

travail de la règle de la production,

S -> ab | aSb 

nous pourrions écrire

s = ["ab"] ++ [ "a" ++ x ++ "b" | x <- s ] 

afin que

~> take 5 s 
["ab","aabb","aaabbb","aaaabbbb","aaaaabbbbb"] 
it :: [[Char]] 

Votre tentative pourrait travailler avec une petite modification,

[ x ++ y | x <- ["a","aa",..] | y <- ["b","bb",..]] 

afin qu'il utilise l'extension Parallel List Comprehensions (:set -XParallelListComp en GHCi), à l'exception des énumérations. Mais c'est simple à corriger,

[ x ++ y | x <- [replicate n 'a' | n <- [1..]] 
     | y <- [replicate n 'b' | n <- [1..]]]