Ngôn ngữ cân bằng, 2 Ký hiệu không phải là thiết bị đầu cuối, Danh sách hiểu

Question

Vì vậy, tôi đã đọc một cuốn sách, "Giới thiệu về lý thuyết ngôn ngữ chính thức" và nó mô tả một ngôn ngữ L(G) = {a^n ++ b^n | n > 0}.

Nó có tác phẩm sau đây:

S -> ab | aSb 

Và như vậy sẽ tạo ra các ngôn ngữ sau:

a, ab, aabb, aaabbb, ... 

tôi đã tự hỏi làm thế nào tôi có thể sử dụng danh sách hiểu Haskell để tạo ra ngôn ngữ này. Tôi biết tôi có thể làm danh sách hiểu với dây, nhưng tôi khá nhiều người mới bắt đầu và không chắc chắn làm thế nào tôi có thể nhận được một danh sách vô hạn như tôi muốn của các dây.

Tôi đang tưởng tượng cái gì đó như:

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

Answer 1

Làm việc từ sự cai trị sản xuất,

S -> ab | aSb 

chúng ta có thể viết

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

để

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

nỗ lực của bạn có thể làm việc với một chỉnh sửa nhỏ,

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

để nó sử dụng Parallel List Comprehensions mở rộng (:set -XParallelListComp trong GHCi), trừ các kiểu liệt kê. Nhưng điều này rất đơn giản để khắc phục,

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