Balanced Language, 2 Non-Terminal Symbols, List Comprehension

user_6189164 0
Viewed 91

So, I was reading a book, "An Introduction to Formal Language Theory" and it describes a language L(G) = {a^n ++ b^n | n > 0}.

It has the following productions:

S -> ab | aSb

And so would produce the following language:

a, ab, aabb, aaabbb, ...

I was wondering how I could use Haskell's list comprehension to create this language. I know I can do list comprehension with strings, but I'm pretty much of a beginner and wasn't sure how I could get an infinite list like I would like of these strings.

I'm imagining something like:

[ x ++ y | x <- ["a","aa",..] y <- ["b","bb",..]]
list-comprehension haskell
1 Answers

Working from the production rule,

S -> ab | aSb

we could write

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

so that

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

Your attempt could work with a small edit, 

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

so that it uses Parallel List Comprehensions extension (:set -XParallelListComp in GHCi), except for the enumerations. But this is simple to fix,

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