Sökning: onr:"swepub:oai:DiVA.org:umu-88231" >
Characterizing Non-...
Characterizing Non-Regularity
-
- Berglund, Martin, 1981- (författare)
- Umeå universitet,Institutionen för datavetenskap,Naturliga och Formella Språk
-
- Björklund, Henrik, 1973- (bidragsgivare)
- Umeå universitet,Institutionen för datavetenskap,Naturliga och Formella Språk
-
- Drewes, Frank, 1963- (bidragsgivare)
- Umeå universitet,Institutionen för datavetenskap,Naturliga och Formella Språk
-
(creator_code:org_t)
- Umeå : Umeå universitet, 2014
- Engelska 9 s.
-
Serie: Report / UMINF, 0348-0542 ; 14.12
- Relaterad länk:
-
https://urn.kb.se/re...
Abstract
Ämnesord
Stäng
- This paper considers a characterization of the context-free non-regular languages, conjecturing that there for all such languages exists a fixed string thatcan be pumped to exhibit infinitely many equivalence classes. A proof is given only for a special case, but the general statement is conjectured to hold. The conjecture is then shown to imply that the shuffle of two context-free languagesis not context-free.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- context-free languages
- characterization
- regular languages
- pumping lemma
- shuffle
- Computer Science
- datalogi
Publikations- och innehållstyp
- vet (ämneskategori)
- rap (ämneskategori)