Ответ. Пусть из L выводится любое слово вида 00..00, а из M выводится лишь слово 01. Тогда из K выводится слово 00001, но процедура ReadK этого не заметит.

Укажем достаточноые условия корректности процедуры ReadK. Для этого нам понадобятся некоторые обозначения. Пусть фиксированы КС-грамматика и некоторый нетерминал № этой грамматики. Рассмотрим №‑слово A, которое имеет собственное начало B, также являющееся №‑словом (если такие есть). Для любой пары таких слов A и B рассмотрим терминальный символ, идущий в A непосредственно за B. Множество всех таких терминалов обозначим Посл(N). (Если никакое №‑слово не является собственным началом другого №‑слова, то множество Посл(N) пусто.)

5.4.2. Указать (а) Посл(E) для примера 1; (б) Посл(E) и Посл(T) для примера 2; (в) Посл(<слаг>) и Посл(<множ>) для примера 3.

Ответ. (а) Посл(e) = { [, ( }. (б) Посл(e) = { [, ( }; Посл(t) пусто (никакое t‑слово не является началом другого). (в) Посл(<слаг>) = {*}; Посл(<множ>) пусто.

Кроме того, для каждого нетерминала № обозначим через Нач(N) множество всех терминалов, являющихся первыми буквами непустых №‑слов. Это обозначение —вместе с предыдущим —позволит дать достаточное условие корректности процедуры ReadK в описанной выше ситуации.

5.4.3. Доказать, что если Посл (L) не пересекается с Нач(M) и множество всех M‑слов непусто, то ReadK корректна.

Решение. Рассмотрим два случая. (1) Пусть после ReadL значение переменной b ложно. В этом случае ReadM читает со входа максимальное M‑начало A, не являющееся M‑словом. Оно является K‑началом (здесь важно, что множество L‑слов непусто.). Будет ли оно максимальным K‑началом среди начал входа? Если нет, то A является началом слова BC, где B есть L‑слово, C есть M‑начало и BC —более длинное начало входа, чем A. Если B длиннее A, то A —не максимальное начало входа, являющееся L‑началом, что противоречит корректности ReadL. Если B = A, то A было бы L‑словом, а это не так. Значит, B короче A, C непусто и первый символ слова C следует в A за последним символом слова B, т.е. Посл(L) пересекается с Нач(M). Противоречие. Итак, A максимально. Из сказанного следует также, что A не является K‑словом. Корректность процедуры ReadK в этом случае проверена.

(2) Пусть после ReadL значение переменной b истинно. Тогда прочитанное процедурой ReadK начало входа имеет вид AB, где A есть L‑слово, а B есть M‑начало. Тем самым AB есть K‑начало. Проверим его максимальность. Пусть C есть большее K‑начало. Тогда либо C есть L‑начало (что невозможно, так как A было максимальным L‑началом), либо C = A'B', где A' —L‑слово, B' —M‑начало. Если A' короче A, то B' непусто и начинается с символа, принадлежащего и Нач(M), и Посл(L), что невозможно. Если A' длиннее A, то это противоречит тому, что A было максимальным. Итак, A' = A. Но в этом случае B' есть продолжение B, что противоречит корректности ReadM. Итак, AB —максимальное K‑начало. Остается проверить правильность выдаваемого процедурой ReadK значения переменной b. Если оно истинно, то это очевидно. Если оно ложно, то B не есть M‑слово, и надо проверить, что AB —не K‑слово. В самом деле, если бы выполнялось AB = A'B', где A' —L‑слово, B' —M‑слово, то A' не может быть длиннее A (ReadL читает максимальное слово), A' не может быть равно A (тогда B' равно B и не является M‑словом) и A' не может быть короче A (тогда первый символ B' принадлежит и Нач(M), и Посл(L)). Задача решена.