Нерегулярность и КС-анализ
تم الإنشاء في: ١٢ يناير ٢٠٢٥
تم الإنشاء في: ١٢ يناير ٢٠٢٥
Базовые задания
Дано описание языка (два — словесных, одно —
атрибутное).
1 Если язык регулярный — привести или регулярку, или
автомат (4 балла) и проверить префикс-свойство (1 балл)
2 Если язык детерминированный КС — привести DPDA или
LL(k)-грамматику (4 балла) и доказать нерегулярность (1
балл).
3 Если язык недетерминированный КС — привести
произвольный PDA или грамматику (2 балла) и доказать
недетерминированность (3 балла).
4 Если язык не КС, описан атрибутно — доказать, что не КС (3
балла), а также привести его словесное описание (2 балла).
5 Если язык не КС, описан не атрибутно — доказать, что не
КС (3 балла), привести атрибутную грамматику (2 балла).
1 / 5
▲
Дополнительные задания
Оцениваются каждое до +5 баллов. Если базовая задача лёгкая
(например, регулярка очень простая), то максимум может и не
достигаться.
1 Если язык регулярный — проанализировать размер минимального
НКА; построить 1-однозначную регулярку (не всегда это
возможно); проверить минимальное число классов
эквивалентности, если бы язык был VPL.
2 Если язык детерминированный КС — проанализировать на
LL-свойство, проанализировать на префикс-свойство,
проанализировать, является ли он VPL.
3 Если язык недетерминированный КС — проверить, является ли он
линейным; проверить, выполняется ли префикс-свойство;
проверить, является ли КС-языком его дополнение.
4 Если язык не КС — проверить префикс-свойство, привести
альтернативные доказательства не КС, построить расширенный
regex или конъюнктивную грамматику, проверить на КС-свойство
его дополнение.
2 / 5
▲
Лайфхаки
Если язык КС, но не понятно, детерминированный или нет — строить
произвольную грамматику или PDA и в любом случае получить за это 2
балла.
Если префикс-свойство не совсем тривиальное — проверить его и точно
добавить себе 1 балл.
Доказательство нерегулярности языка, если он КС — тоже
гарантированный 1 балл (но 0 баллов, если язык — не КС).
Если язык не является DCFL — анализ дополнения принесёт допбаллы
почти всегда, за исключением случая, когда он совсем тривиальный.
Если язык судя по всему не КС, но не удаётся это доказать, зато удалось
доказать, что он не DCFL — всё равно будет 1 балл.
Если удалось доказать, что язык не LL, но не удаётся доказать, что он не
DCFL — это потеря всего 1 балла из 3 возможных.
Если удалось доказать, что язык не VPL, но не удаётся понять, DCFL ли
он — 1 балл получен всё равно.
3 / 5
▲
Размер минимального НКА
Уточнённая теорема Глайстера-Шаллита: если существуют N
префиксов γ1,..., γN и N суффиксов ω1,...,ωN таких, что
∀i, j(γiωi ∈ L & (j > 0 ⇒ γi−jωi ∈/ L )), то размер
минимального НКА не меньше, чем N.
Пример — a(a|b)
∗a|b(a|b)
∗b.
КЭ по Майхиллу–Нероде:
ε a b aa bb
ε 0 0 0 1 1
a 0 1 0 1 0
b 0 0 1 0 1
aa 1 1 0 1 0
bb 1 0 1 0 1
Приближённые КЭ НКА:
aa a b ε
ε 1 0 0 0
a 1 1 0 0
b 0 0 1 0
aa 1 1 0 1
NB: бывают языки с неточной оценкой КЭ НКА по этой теореме.
4 / 5
▲
Размер минимального НКА
Пусть нашлась треугольная матрица таких γ1,..., γN; ω1,...,ωn. Тогда,
если префиксы γi и γi+j будут всегда вместе присутствовать в одном и
том же состоянии НКА, то из него станет возможно распознать слово
γiωi+j, которое согласно таблице языку не принадлежит. То k-ая
строка в таблице определяет префиксный КЭ, достигаемый хотя бы в
одном состоянии, не достижимом по всем классам из 1...k − 1 строк.
ε
a, aa
aa, bb
b, bb
a, b
a a
b
a, b
b
Если построить НКА с 4 состояниями, распознающими a(a|b)
∗a|b(a|b)
∗b,
можно увидеть, что финальное состояние достижимо только по префиксу aa.
То, что по нему также достижимо состояние, соответствующее префиксу a, показывает, что в таблице приближённых
КЭ a может стоять только выше, чем aa.
Заметим, что префикс bb не определяет никакого состояния, не
достижимого по остальным префиксам, поэтому на размер НКА его
наличие в таблице КЭ по Майхиллу-Нероде не влияет.
Язык SRS (string rewriting system) с правилами abb -> ababa bac -> caa a -> cc cb -> 𝜀 (пустое слово)
базис - a^nb^(n+k)
Для работы с данным языком SRS и базисом , нужно выполнить следующие шаги в зависимости от его классификации.
Проверим, является ли язык регулярным. Если язык регулярный, то для любого описания строк существует конечное число состояний автомата. Однако, с учетом правил переписывания и базиса :
Эти правила предполагают, что зависимость между числами и сохраняется. Таким образом, язык не является регулярным, поскольку невозможно реализовать конечный автомат, который учитывал бы эту зависимость.
Используем лемму о накачке. Для базиса :
Теперь проверим, является ли язык контекстно-свободным (КС). Для этого можно построить грамматику.
Объяснение:
Контекстно-свободный автомат (PDA) должен принимать строки . Однако из-за взаимозависимости и PDA должен проверять как баланс , так и наличие , что невозможно сделать однозначно. Таким образом, язык является недетерминированным КС.
Используем свойства DCFL:
Дополнение потребует проверки строк с нарушением:
Это требует хранения дополнительной информации в PDA, что невозможно для детерминированного PDA. Следовательно, язык не DCFL.
Базовые задания
Дано описание языка (два — словесных, одно —
атрибутное).
1 Если язык регулярный — привести или регулярку, или
автомат (4 балла) и проверить префикс-свойство (1 балл)
2 Если язык детерминированный КС — привести DPDA или
LL(k)-грамматику (4 балла) и доказать нерегулярность (1
балл).
3 Если язык недетерминированный КС — привести
произвольный PDA или грамматику (2 балла) и доказать
недетерминированность (3 балла).
4 Если язык не КС, описан атрибутно — доказать, что не КС (3
балла), а также привести его словесное описание (2 балла).
5 Если язык не КС, описан не атрибутно — доказать, что не
КС (3 балла), привести атрибутную грамматику (2 балла).
1 / 5
▲
Дополнительные задания
Оцениваются каждое до +5 баллов. Если базовая задача лёгкая
(например, регулярка очень простая), то максимум может и не
достигаться.
1 Если язык регулярный — проанализировать размер минимального
НКА; построить 1-однозначную регулярку (не всегда это
возможно); проверить минимальное число классов
эквивалентности, если бы язык был VPL.
2 Если язык детерминированный КС — проанализировать на
LL-свойство, проанализировать на префикс-свойство,
проанализировать, является ли он VPL.
3 Если язык недетерминированный КС — проверить, является ли он
линейным; проверить, выполняется ли префикс-свойство;
проверить, является ли КС-языком его дополнение.
4 Если язык не КС — проверить префикс-свойство, привести
альтернативные доказательства не КС, построить расширенный
regex или конъюнктивную грамматику, проверить на КС-свойство
его дополнение.
2 / 5
▲
Лайфхаки
Если язык КС, но не понятно, детерминированный или нет — строить
произвольную грамматику или PDA и в любом случае получить за это 2
балла.
Если префикс-свойство не совсем тривиальное — проверить его и точно
добавить себе 1 балл.
Доказательство нерегулярности языка, если он КС — тоже
гарантированный 1 балл (но 0 баллов, если язык — не КС).
Если язык не является DCFL — анализ дополнения принесёт допбаллы
почти всегда, за исключением случая, когда он совсем тривиальный.
Если язык судя по всему не КС, но не удаётся это доказать, зато удалось
доказать, что он не DCFL — всё равно будет 1 балл.
Если удалось доказать, что язык не LL, но не удаётся доказать, что он не
DCFL — это потеря всего 1 балла из 3 возможных.
Если удалось доказать, что язык не VPL, но не удаётся понять, DCFL ли
он — 1 балл получен всё равно.
3 / 5
▲
Размер минимального НКА
Уточнённая теорема Глайстера-Шаллита: если существуют N
префиксов γ1,..., γN и N суффиксов ω1,...,ωN таких, что
∀i, j(γiωi ∈ L & (j > 0 ⇒ γi−jωi ∈/ L )), то размер
минимального НКА не меньше, чем N.
Пример — a(a|b)
∗a|b(a|b)
∗b.
КЭ по Майхиллу–Нероде:
ε a b aa bb
ε 0 0 0 1 1
a 0 1 0 1 0
b 0 0 1 0 1
aa 1 1 0 1 0
bb 1 0 1 0 1
Приближённые КЭ НКА:
aa a b ε
ε 1 0 0 0
a 1 1 0 0
b 0 0 1 0
aa 1 1 0 1
NB: бывают языки с неточной оценкой КЭ НКА по этой теореме.
4 / 5
▲
Размер минимального НКА
Пусть нашлась треугольная матрица таких γ1,..., γN; ω1,...,ωn. Тогда,
если префиксы γi и γi+j будут всегда вместе присутствовать в одном и
том же состоянии НКА, то из него станет возможно распознать слово
γiωi+j, которое согласно таблице языку не принадлежит. То k-ая
строка в таблице определяет префиксный КЭ, достигаемый хотя бы в
одном состоянии, не достижимом по всем классам из 1...k − 1 строк.
ε
a, aa
aa, bb
b, bb
a, b
a a
b
a, b
b
Если построить НКА с 4 состояниями, распознающими a(a|b)
∗a|b(a|b)
∗b,
можно увидеть, что финальное состояние достижимо только по префиксу aa.
То, что по нему также достижимо состояние, соответствующее префиксу a, показывает, что в таблице приближённых
КЭ a может стоять только выше, чем aa.
Заметим, что префикс bb не определяет никакого состояния, не
достижимого по остальным префиксам, поэтому на размер НКА его
наличие в таблице КЭ по Майхиллу-Нероде не влияет.
Язык SRS (string rewriting system) с правилами abb -> ababa a -> cc cb -> 𝜀 (пустое слово)
базис - a^nb^(n+k)
Ниже приведён разбор задачи о языке, заданном переписными правилами (SRS)
с «базисом» (словесным описанием) вида
Поясним, почему это именно язык вида и как он классифицируется согласно заданным критериям.
Условно можно считать, что правила SRS задают всевозможные переписывания, которые в итоге (после достаточного числа шагов) приводят строки к виду . В задаче заранее (в тексте) упомянуто, что «базис» у языка именно такой:
Параметр считается фиксированным положительным числом (или хотя бы не зависящим от ), и тогда любая допустимая в языке строка имеет ровно на символов больше, чем символов .
При этом порядок символов в строке строго всех сначала, а всех — потом; никаких «смешанных» вкраплений и в произвольном порядке нет. Таким образом, «словесно» язык можно сформулировать так:
Словесное описание: «Все строки из нуля или более символов , за которыми следует ровно на символов больше, чем было ».
Иными словами, если общее число равно , то общее число равно .
Чтобы показать, что нерегулярен, можно воспользоваться леммой о накачке (pumping lemma) или рассуждением по Майхиллу–Нероде.
Значит, нерегулярен.
Теперь нужно показать, что язык не только контекстно-свободен, но и детерминированно контекстно-свободен (DCFL).
Пусть зафиксировано. Опишем грамматику , которая порождает ровно строки вида . Мы хотим, чтобы грамматика была удобна для детерминированного восходящего или нисходящего анализа (LL(1) или LR(1)). Один из простых вариантов:
Начальный нетерминал .
Правила:
где отвечает за «добивку» недостающих штук .
Нетерминал порождает ровно символов . Формально, если хотим это зафиксировать в самой грамматике, выписываем:
Итого ровно раз символ .
(Или схематически пишут , подразумевая «точно b-шек».)
Как эта грамматика порождает ?
Таким образом, конфликта при выборе продукции нет, грамматика действительно LL(1). Это автоматически даёт и детерминированность при построении соответствующего PDA.
Детерминированный магазинный автомат (DPDA), принимающий , может работать так:
Такой автомат однозначно, без бэктрекинга, проверяет:
Таким образом, язык является (детерминированным КС-языком).
Таким образом, по критериям из условия это ровно случай 2:
«Если язык детерминированный КС — привести DPDA или LL(k)-грамматику (4 балла) и доказать нерегулярность (1 балл).»
Все требования выполнены:
Можно также упомянуть, что раз язык DCFL, то и обычная «произвольная» КС-грамматика, и НКА (конечный автомат) для него в принципе не подходят (НКА точно не существует, так как язык нерегулярен).
Таким образом, задача классификации полностью решена.