|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Swapping Lemmas for Regular and Context-Free Languages with Advice | | Tomoyuki Yamakami
; | | Date: |
29 Aug 2008 | | Abstract: | Chomsky studied regular languages and context-free languages to develop his
theory of formal languages. These languages are generated by restricted forms
of grammars and also characterized by finite-state automata. Karp and Lipton
examined roles of supplemental information given besides original inputs, under
the term of "advice," which depends only on the size of the inputs. We study
the power and limitation of such advice, when it is given to automata. A
standard pumping lemma in formal language theory is, however, of no use in
order to prove that a given language is not regular with advice. We develop its
substitution, called a swapping lemma for regular languages, to prove the
non-regularity of the 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. | | Source: | arXiv, 0808.4122 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER