Рекурсивное определение для языка

Question

Предположим, у меня есть язык, состоящий из сбалансированных круглых скобок, т.е. {ε,(), (()),()(), (())), (()()), ...}, и меня попросят написать для него рекурсивное определение. Может ли кто-нибудь дать мне пример того, как это могло бы выглядеть? - Я немного новичок в этом типе теории компьютерных наук.

Answer 1

Рекурсивное определение - это грамматика. Для создания языка сбалансированных скобок:

S --> (S) | SS |^

это рекурсивная, потому что S появляется в RHS продукционных правил.

производственные правила: LHS --> RHS

EDIT

Почему (s) не S?

потому что нужно добавить () пар рекурсивно и более одного раза.

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

на втором этапе внутренняя S заменяется (S).

Answer 2

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