Pumping Lemma and Ogden Lemma for Displacement Context-Free Grammars

Автор: Sorokin Alexey
Сборник: Developments in Language Theory - 18th International Conference (DLT), 2014, Ekaterinburg, Russia, August 26-29, 2014. Proceedings
Серия: Lecture Notes in Computer Science
Том: 8633
Год издания: 2014
Издательство: SPRINGER-VERLAG BERLIN
Местоположение издательства: HEIDELBERGER PLATZ 3, BERLIN, GERMANY,D-14197
Первая страница: 154
Последняя страница: 165
DOI: 10.1007/978-3-319-09698-8_14
Аннотация: The pumping lemma and Ogden lemma offer a powerful method to prove that a particular language is not context-free. In 2008 Kanazawa proved an analogue of pumping lemma for well-nested multiple context-free languages. However, the statement of lemma is too weak for practical usage. We prove a stronger variant of pumping lemma and an analogue of Ogden lemma for this language family. We also use these statements to prove that some natural context-sensitive languages cannot be generated by tree-adjoining grammars.
Добавил в систему: Сорокин Алексей Андреевич

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ПсковГУ
	Главная Поиск Статистика О проекте Помощь

ИСТИНА