Swapping Lemmas for Regular and Context-Free Languages
| dc.creator | Yamakami, Tomoyuki | |
| dc.date | 2008-08-29 | |
| dc.date | 2009-03-05 | |
| dc.date.accessioned | 2026-07-07T12:48:51Z | |
| dc.date.available | 2026-07-07T12:48:51Z | |
| dc.description | In formal language theory, one of the most fundamental tools, known as pumping lemmas, is extremely useful for regular and context-free languages. However, there are natural properties for which the pumping lemmas are of little use. One of such examples concerns a notion of advice, which depends only on the size of an underlying input. A standard pumping lemma encounters difficulty in proving that a given language is not regular in the presence of advice. We develop its substitution, called a swapping lemma for regular languages, to demonstrate the non-regularity of a target language with advice. For context-free languages, we also present a similar form of swapping lemma, which serves as a technical tool to show that certain languages are not context-free with advice. | |
| dc.description | Version 2: minor chages associated with typos; slight changes of title, abstract, and introduction (letter size, 13 pages, 4 figures) | |
| dc.identifier | https://arxiv.org/abs/0808.4122 | |
| dc.identifier | http://arxiv.org/abs/0808.4122 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/222202 | |
| dc.subject | Computational Complexity | |
| dc.subject | Computation and Language | |
| dc.subject | Formal Languages and Automata Theory | |
| dc.title | Swapping Lemmas for Regular and Context-Free Languages | |
| dc.type | text |