Interchange lemma
Jump to navigation
Jump to search
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
In the theory of formal languages, the interchange lemma states a necessary condition for a language to be context-free, just like the pumping lemma for context-free languages.
It states that for every context-free language there is a such that for all for any collection of length words there is a with , and decompositions such that each of , , is independent of , moreover, , and the words are in for every and .
The first application of the interchange lemma was to show that the set of repetitive strings (i.e., strings of the form with ) over an alphabet of three or more characters is not context-free.
See also
References
- William Ogden, Rockford J. Ross, and Karl Winklmann (1982). "An "Interchange Lemma" for Context-Free Languages". SIAM Journal on Computing. 14 (2): 410–415. doi:10.1137/0214031.
{{cite journal}}
: CS1 maint: multiple names: authors list (link)
Categories:
- Articles lacking reliable references from March 2019
- All articles lacking reliable references
- Articles lacking in-text citations from September 2022
- All articles lacking in-text citations
- Articles with multiple maintenance issues
- CS1 maint: multiple names: authors list
- Formal languages
- Lemmas
- All stub articles
- Grammar stubs