Насосная лемма для детерминированных контекстно-свободных языков?

11

Насосная лемма для регулярных языков может быть использована для доказательства того, что некоторые языки не являются регулярными, а прокачивающая лемма для контекстно-свободных языков (наряду с леммой Огдена) может быть использована для доказательства того, что некоторые языки не являются контекстно-свободными.

Существует ли накачка леммы для детерминированных контекстно-свободных языков? То есть, существует ли лемма, сродни лемме накачки, которая может использоваться, чтобы показать, что язык не является DCFL? Мне любопытно, потому что почти все методы проверки, которые я знаю, чтобы показать, что язык не является DCFL, действительно сложны, и я надеялся, что там была более простая методика.

templatetypedef
источник
2
Есть некоторые связанные вопросы, которые могут быть или не быть актуальными.
Рафаэль
Компьютерные ученые могут быть садистами, но они не все мазохисты, которые используют слишком сложные методы доказательства, где известны более простые ...
vonbrand
1
vonbrand: Но любой математик или компьютерный ученый может использовать слишком сложные методы доказательства, если более простые из них еще не известны или ему неизвестны.
Blaisorblade

Ответы:

9

Там является насосная лемма специально для DCFL, под названием «насосная лемму для детерминированных контекстно-свободных языков», Шэн Ю.; Письма для обработки информации 31 (1989) 47-51, doi 10.1016 / 0020-0190 (89) 90108-7 . С таким явным названием я должен извиниться, что пропустил это!

К сожалению, в онлайн-копии в одной из формул есть пустое место, поэтому я надеюсь, что восстановил результат должным образом. Нижеявляется первым символомy(когда он существует) илиε(еслиy=ε).(1)YYεYзнак равноε

Лемма 1 (прокачка леммы). Пусть будет DCFL. Тогда существует константа C для L такая, что для любой пары слов w , w ∈, еслиLСLвес,вес'

(1) [?] И w = x z , | х | > С ивесзнак равноИксYвес'знак равноИксZ|Икс|>С

(2) , [?](1)Yзнак равно(1)Z

тогда либо (3), либо (4) верно:

(3) существует факторизация , | х 2 х 4 | 1 и | х 2 х 3 х 4 | C , такой что для всех i 0 x 1 x i 2 x 3 x i 4 x 5 y и x 1 x i 2 xИксзнак равноИкс1Икс2Икс3Икс4Икс5|Икс2Икс4|1|Икс2Икс3Икс4|Ся0 Икс1Икс2яИкс3Икс4яИкс5Y находятся в L ;Икс1Икс2яИкс3Икс4яИкс5ZL

Иксзнак равноИкс1Икс2Икс3Yзнак равноY1Y2Y3Zзнак равноZ1Z2Z3|Икс2|1|Икс2Икс3|Ся0 Икс1Икс2яИкс3Y1Y2яY3Икс1Икс2яИкс3Z1Z2яZ3L

{aябя|я0}{aяб2я|я0}{вес{a,б}*|весзнак равноUv,|U|знак равно|v|, а также v содержит a}не DCFL. В доказательстве используется тот факт, что каждый DCFL имеет грамматику LR (1) в нормальной форме Грейбаха.

Хендрик Ян
источник
Я надеюсь, что вы можете использовать это. Это еще сложнее сформулировать, чем известная лемма прокачки.
Хендрик Янв