Указание языка для грамматики - PullRequest
Новая
       9

Указание языка для грамматики

1 голос
/ 29 мая 2010

Есть ли какая-то конкретная методика, используемая для указания языка для данной грамматики? Т.е. необходимо ли запускать все производственные правила, приведенные в грамматике, чтобы определить язык, который она представляет? У меня нет такого примера, так как тот, над которым я работаю, - это домашнее задание. 

[edit]: adding an example, Describe, in English, the language defined by the grammar

    <S> -> <A> <B> <C>
         <A> -> a <A> | a
         <B> -> b <B> | b
         <C> -> c <C> | c

С уважением,

darkie15

1 Ответ

1 голос
/ 29 мая 2010

В вашем примере, часть 

<A> -> <A> a | a

точно распознает непустые списки a То же самое касается двух других постановок, <B> и <C>, с соответственно b и c.

Таким образом, с помощью <S> -> <A> <B> <C> вы выводите, что язык, который распознает эта грамматика, представляет собой любой непустой список a, за которым следует непустой список b, затем непустой список c, соответствующий к регулярному выражению a+b+c+.

Отсюда довольно легко доказать, что каждый экземпляр, распознаваемый регулярным выражением, распознается грамматикой с использованием индукции.

...