Может ли кто-нибудь объяснить эту контекстно-свободную грамматику?

Question

Мне нужно понять это для домашней работы. Вы бы не дали мне ответ, сказав мне это, вы просто поможете мне понять вопрос, который задают.

Я прочитал свои заметки о классе, которые не были очень полезными, а также поиск по всему Интернету для контекстной информации грамматики. Я не могу найти ничего похожего на то, что мне дано, и я очень смущен.

Если кто-нибудь может сказать мне, что описывает этот CFG, или дать мне хороший ресурс, чтобы объяснить эту тему, я был бы очень признателен.

Грамматика CFG заключается в следующем:

S является начальным символом

<S> → <A> | ε 
<A> → 0<B> | 1<A> 
<B> → 0<C> | 1<B> 
<C> → 0<D> | 1<C> 
<D> → 1<D> | 0<B> | ε 

Answer 1

CFG определяет образцы строки.

Здесь строка может быть образцом 1,0, e. (Алфавиты) Правила CFG рассказывают, как развернуть выражения в строки алфавитов.

<S> → <A> | ε 
<A> → 0<B> | 1<A> 
<B> → 0<C> | 1<B> 
<C> → 0<D> | 1<C> 
<D> → 1<D> | 0<B> | ε 

Здесь A может быть расширена до 0B или 1A. LHS можно расширить.

С учетом строки вы можете проверить, описано ли это CFG или нет.

Позволяет взять 1000 и посмотреть, описан ли он этим CFG или нет.

Начнем с S, который может расширяться до A или e.

expr = S 

e - специальный символ, который говорит о его прекращении строки. Мы будем использовать A, поскольку он дает нам надежду вместо завершения с e.

expr = A  (S ->A) 

A может расшириться до 0B или 1A. Для нашей строки мы будем использовать 1A.

expr = 1A  (A ->1A) 

Теперь 1A имеет A. Глядя вверх в таблицу правил A, можно развернуть до 0B или 1A. Мы возьмем 0B, как следует данной строке. Итак, теперь наш результат 10B.

expr = 10B (A -> 0B) 

Lookup B, который расширяется до 0C или 1B. Мы возьмем 0C, поскольку он соответствует нашему шаблону. Поэтому наша строка становится 100C.

expr = 100C (B -> 0C) 

Аналогичным образом вы можете продолжить расширение выражения и завершить его с помощью e.

expr = 1000D (C -> 0D) 
expr = 1000e (D -> e) 

Answer 2

CFG: Контекстно-свободная грамматика (CFG) это термин, используемый в теории формальных языков для описания определенного типа формального grammar.In контекстно-свободных грамматик, все правила один к одному, один для многих или от одного до одного. Язык, созданный контекстно-свободными грамматиками, известен как контекстно-свободные языки (CFL). Различные контекстно-свободные грамматики могут генерировать один и тот же контекстно-свободный язык.Важно отличить свойства языка от свойств конкретной грамматики. Вопрос о языковом равенстве (сделать две заданные контекстно-свободные грамматики порождают один и тот же язык?) Неразрешима.

Выше линии выбраны часть из CFG

Короче говоря, из любого CFG дано попытаться выяснить набор строк, которые могут быть описаны в этой CFG. Этот набор строк делает язык этого конкретного CFG.

Ниже решение вашего вопроса в графической форме:

В растворе строки в прямоугольных коробках шаги согласующие.

Таким образом, данный CFG может иметь строки, как:

{100, 0100, 1001, 1010, 01001, 10011, 10101, 010011, 0100111, ......}

Так что это CFG может иметь любой тип строки, которая имеет:

1. по меньшей мере, один 1,
2. по меньшей мере, два 0, а

3. длина> = 3, так как при наблюдении мы получаем минимальную длину й кольцо может быть 100:

   S --> A --> 1B --> 10C --> 100D --> 100e --> 100 
   

И наблюдая за ниточки на каждом шаге вы можете легко получить, что CFG может иметь любой тип строк, который имеет над тремя свойствами.

Итак, этот CFG описывает свободный текст контекста, который имеет более 3 свойств.