c - C语言中的上下文无关文法

我有一个任务要用C编写一个程序，该程序使用以下上下文无关语法显示一个有效的上下文无关语法字符串（n

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

我对怎么做没有什么概念，但经过越来越多的分析，没有一个是正确的。
现在，我计划创建一个数组，并随机改变[..., A, ...]以获得[..., S, S, ...]或[..., 1, ...]直到只有0和1，然后检查是否已经随机生成了相同的东西。
我仍然不确定这是否是正确的方法，我仍然不知道如何做到这一点，也不知道在哪里保留最后的单词，因为基本形式将是不同长度的字符数组。另外，在C语言中，二维字符数组是否等于字符串数组？
这有什么意义吗？这是一个正确的方法吗？还是我遗漏了什么？

最佳答案

你只需在每次需要做决定的时候做一个随机的决定。例如：

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"。