C 中的上下文无关文法

Question

我有一项任务是用 C 编写一个程序，该程序使用以下上下文无关语法显示一定数量 (n < 50) 的有效上下文无关语法字符串:

S -> AA|0
A -> SS|1

我对如何做几乎没有概念，但在越来越多地分析之后，它们都不对。

现在，我打算制作一个数组并随机更改 [..., A, ...] 为 [..., S, S, .. .] 或 [..., 1, ...] 直到只有 0 和 1，然后检查是否已经随机生成了相同的东西。

我仍然不确定这是否是正确的方法，而且我仍然不知道该怎么做或在哪里保留最后的单词，因为基本形式将是一个不同长度的字符数组。另外，在 C 中，二维字符数组等于字符串数组吗？

这样做有什么意义吗？这是正确的做法吗？还是我遗漏了什么？

Answer 1

每次需要决定某事时，您都可以简单地随机做出决定。例如:

function A():
  if (50% random chance)
    return "1"
  else
    return concat(S(), S())

function S():
  if (50% random chance)
    return "0"
  else
    return concat(A(), A())

多次调用 S() 会得到这些输出:

"0"
"00110110100100101111010111111111001111101011100100011000000110101110000110101110
 10001000110001111100011000101011000001101111000110110011101010111111111011010011
 10000000101111100100011011010000000101000111110010001000101001100110100111111111
 1001010011"
"11"
"10010010101111010111101"

语法的所有有效字符串。请注意，您可能需要稍微调整一下随机机会。此示例很有可能生成非常小的字符串，例如 "11"。