Докажите, что следующие языки эквивалентны - PullRequest
Новая
       18

Докажите, что следующие языки эквивалентны

0 голосов
/ 31 марта 2019

Мне нужно доказать, что следующие языки эквивалентны по индукции:

P :: = ε | id | (P)

и

S :: = ε | id | (R

R :: =) | S)

Нужно доказать, что:

L (P) = L (S)

как я могу это сделать?

Мне удалось доказать, что L (S) содержит L (P), но я не могу доказать другое направление.

1 Ответ

0 голосов
/ 01 апреля 2019

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

Нашеутверждение может быть «L (P) и L (S) содержат одинаковые строки длины n для всех натуральных n».

Наши базовые случаи могут быть наименьшими наименьшими строками на обоих языках: L (P) иL (S) оба содержат пустую строку, единственную строку нулевой длины;таким образом, утверждение верно для случая n = 0. И L (P), и L (S) содержат id, единственную строку на языке длины два (при условии, что i и d - разные символы; если id - один символ, то этистроки имеют длину один).Таким образом, утверждение имеет место до n = 2 (или n = 1, в зависимости от).

Мы можем использовать сильную индукцию, а не простую индукцию, следующим образом: L (P) и L (S) содержат всете же строки длиной до k.

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

  1. Пусть w будет строкой следующей за более высокой длины в L (P).Первым произведением, использованным для получения w, должно было быть P :: = (P), поскольку | w |> 2 (или | w |> 1), и мы уже рассмотрели меньшие случаи.Тогда w = (w '), где w' - строка в L (P) и | w '|<| w |.Но w имел следующую длину больше, чем k в L (P), поэтому w 'должно иметь длину, меньшую или равную k.Но тогда, по предположению индукции, w 'должно быть в L (P) и L (S).Таким образом, вывод S :: = (R :: = (S) :: = (w ') действителен и выдает w. Итак, w находится в L (S). </li>
  2. Пусть w - строкаследующей более высокой длины в L (S). Первая продукция, используемая для получения w, должна быть S :: = (R, а следующая продукция должна быть либо R :: =), либо R :: = S).Рассмотрим эти случаи отдельно.
    • если вторым произведением был R :: =), то w = S :: = (R :: = (), который мы можем проверить, есть на обоих языках (или мы можем просто полагаться на индукционную гипотезу).
    • если второе произведение было R :: = S), то w = S :: = (R :: = (S), поэтому w имеет вид (w '), где | w'| <| w |. Поскольку w имеет следующую большую длину, большую, чем k, w 'имеет длину, меньшую или равную k, и генерируется грамматикой для P. </li>
...