recursion - 言語の再帰的定義

Question

{ε, ( ), ( ( ) ), ( ) ( ), ( ( ( ) ) , ( ( ) ( ) ), ... } と私' m は、その再帰的な定義を書くように求められました。誰かがそれがどのように見えるかの例を教えてもらえますか? - 私は、この種のコンピューター サイエンス理論には少し慣れていません。

Answer 1

再帰的な定義の一種が文法です。バランスの取れた括弧の言語を生成するには:

S --> (S) | SS | ^

これは、プロダクション ルール Sに表示されるため、再帰的です。RHS

生産規則: LHS --> RHS

編集

なぜ(s)ですかS？

()ペアを再帰的に複数回 追加するためです。

S --> (S) --->  ((S))   

2 番目のステップで、インナーSは に置き換えられ(S)ます。

Answer 2

TEXT ::= BRACES | BRACKETS | LIST;
BRACES ::= "{" ( TEXT | /* nothing */ ) "}";
BRACKETS ::= "(" ( TEXT | /* nothing */ ) ")";
LIST ::= ( BRACES | BRACKETS ) | ( BRACES | BRACKETS ) "," LIST;