Swapping Lemmas for Regular and Context-Free Languages
arXiv:0808.4122
Abstract
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.
Version 2: minor chages associated with typos; slight changes of title, abstract, and introduction (letter size, 13 pages, 4 figures)
Cited by in corpus (7)
- Immunity and Pseudorandomness of Context-Free Languages
- One-Way Reversible and Quantum Finite Automata with Advice
- Oracle Pushdown Automata, Nondeterministic Reducibilities, and the CFL Hierarchy over the Family of Context-Free Languages
- The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
- Behavioral Strengths and Weaknesses of Various Models of Limited Automata
- Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions
- The Dissecting Power of Regular Languages