INFIX-FREE REGULAR EXPRESSIONS AND LANGUAGES
| Autor: | Yo-Sub Han, Derick Wood, Yajun Wang |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Discrete mathematics
Star height Programming language Context-free language Abstract family of languages Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) computer.software_genre Cone (formal languages) Pumping lemma for regular languages Formal language Computer Science (miscellaneous) Nondeterministic finite automaton Generalized star height problem computer Mathematics |
| Zdroj: | International Journal of Foundations of Computer Science. 17:379-393 |
| ISSN: | 1793-6373 0129-0541 |
| DOI: | 10.1142/s0129054106003887 |
| Popis: | We study infix-free regular languages. We observe the structural properties of finite-state automata for infix-free languages and develop a polynomial-time algorithm to determine infix-freeness of a regular language using state-pair graphs. We consider two cases: 1) A language is specified by a nondeterministic finite-state automaton and 2) a language is specified by a regular expression. Furthermore, we examine the prime infix-free decomposition of infix-free regular languages and design an algorithm for the infix-free primality test of an infix-free regular language. Moreover, we show that we can compute the prime infix-free decomposition in polynomial time. We also demonstrate that the prime infix-free decomposition is not unique. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|