Как я могу найти обычную грамматику для L *, если нам дана грамматика для языка L? - PullRequest
Новая
       6

Как я могу найти обычную грамматику для L *, если нам дана грамматика для языка L?

0 голосов
/ 29 января 2019

Есть ли какой-нибудь общий метод для этого?Например, у нас есть общий метод поиска грамматики для L1 U L2 путем добавления производственной S-> S1 |S2, где S1 и S2 - начальные символы для грамматик L1 и L2 соответственно.Заранее спасибо ..

1 Ответ

0 голосов
/ 13 февраля 2019

В общем, для грамматики G, такой, что L(G) = L', не существует алгоритма, который всегда выдает правильную грамматику G', такую, что L(G') = (L')*.Для начала, (L')* может не быть обычным языком.Даже если вы позволите процедуре распознать этот случай и напечатать «не обычный язык» в таком случае, это не может быть вообще возможным, поскольку это позволит нам определить, генерируют ли произвольные неограниченные грамматики конкретные строки (конструкция не слишком сложная, ноЯ не предоставлю это, если не желаю).Это неразрешимая проблема, поэтому мы не можем распознавать обычные языки в неограниченных грамматиках.

Возможно, ваш вопрос заключается в том, существует ли аккуратная конструкция, чтобы сделать это, если изначально дать обычную грамматику.В этом случае ответ является определенным и ясным, "да!"Вот одна легко описываемая (хотя, возможно, и неэффективная на практике) процедура для этого:

  1. Преобразуйте регулярную грамматику в недетерминированный конечный автомат, используя для этого типичную конструкцию.Существуют простые конструкции для регулярных слева и справа регулярных грамматик.
  2. Построить регулярное выражение из недетерминированного конечного автомата, используя любую известную конструкцию.Одна такая конструкция обычно используется при доказательстве эквивалентности.
  3. Создайте новое регулярное выражение, которое является замыканием Клини, полученного на последнем шаге.
  4. Создайте недетерминированный конечный автомат из регулярного выражения изпоследний шаг, используя стандартную конструкцию.
  5. Построить правильную грамматику из недетерминированного конечного автомата из последнего шага.Для этого существуют известные конструкции.

Таким образом, мы можем механически перейти от обычной грамматики для L к обычной грамматике для L*.

Если вы просто хотите ЛЮБУЮ грамматику дляL*, возможно, проще всего было бы ввести новое начальное состояние S' и производства S' := S'S' | S, где S - начальный символ вашей входной грамматики.Это, очевидно, не дает правильной грамматики, однако - если входная грамматика генерирует обычный язык, этот тоже будет делать это.

Пример: с учетом обычной грамматики 

S := 0S | 1T
T := 0S | 1T | 1

Aконструкция дает нам этот недетерминированный конечный автомат: 

q    s    q'
-    -    -
S    0    S
S    1    T
T    0    S
T    1    T
T    1    (H)

Конструкция дает нам регулярное выражение: 

(0*1)(0*1)*1

Закрытие Клини этого: 

((0*1)(0*1)*1)*

Из стандартной конструкции мы узнаем, что этот автомат эквивалентен: 

q    s    q'
-    -    -
(I)  -    S
S    0    S
S    1    T
T    0    S
T    1    T
T    1    H
H    -    (I)

Откуда следующая регулярная грамматика: 

I := S | -
S := 0S | 1T
T := 0S | 1T | H
H := I
...