Насосная лемма для регулярных языков может быть использована для доказательства того, что некоторые языки не являются регулярными, а прокачивающая лемма для контекстно-свободных языков (наряду с леммой Огдена) может быть использована для доказательства того, что некоторые языки не являются контекстно-свободными.
Существует ли накачка леммы для детерминированных контекстно-свободных языков? То есть, существует ли лемма, сродни лемме накачки, которая может использоваться, чтобы показать, что язык не является DCFL? Мне любопытно, потому что почти все методы проверки, которые я знаю, чтобы показать, что язык не является DCFL, действительно сложны, и я надеялся, что там была более простая методика.
context-free
proof-techniques
pumping-lemma
templatetypedef
источник
источник
Ответы:
Там является насосная лемма специально для DCFL, под названием «насосная лемму для детерминированных контекстно-свободных языков», Шэн Ю.; Письма для обработки информации 31 (1989) 47-51, doi 10.1016 / 0020-0190 (89) 90108-7 . С таким явным названием я должен извиниться, что пропустил это!
К сожалению, в онлайн-копии в одной из формул есть пустое место, поэтому я надеюсь, что восстановил результат должным образом. Нижеявляется первым символомy(когда он существует) илиε(еслиy=ε).( 1 )Y Y ε Y= ε
Лемма 1 (прокачка леммы). Пусть будет DCFL. Тогда существует константа C для L такая, что для любой пары слов w , w ′ ∈, еслиL С L ш , ш'∈
(1) [?] И w ′ = x z , | х | > С иш = х у вес'= х з | х | >C
(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| ≤C я ≥ 0 Икс1Икся2Икс3Икся4Икс5Y находятся в L ;Икс1Икся2Икс3Икся4Икс5Z L
источник