On the Representation and State Complexity of Block Languages
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910946545369088 |
|---|---|
| author | Duarte, Guilherme Moreira, Nelma Prigioniero, Luca Reis, Rogério |
| author_facet | Duarte, Guilherme Moreira, Nelma Prigioniero, Luca Reis, Rogério |
| contents | In this paper, we consider block languages, namely sets of words having the same length, and we propose a new representation for these languages. In particular, given an alphabet of size $k$ and a length $\ell$, a block language can be represented by a bitmap of length $k^\ell$, where each bit indicates whether the corresponding word, according to the lexicographical order, belongs, or not, to the language (bit equal to 1 or 0, respectively). First, we show how to convert bitmaps into deterministic and nondeterministic finite automata, and we prove that the machines are minimal. Then, we give an analysis of the maximum number of states sufficient to accept every block language in the deterministic and nondeterministic case. Finally, we study the deterministic and nondeterministic state complexity of several operations on these languages. Being a subclass of finite languages, the upper bounds of operational state complexity known for finite languages apply for block languages as well. However, in several cases, smaller values were found. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_11746 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Representation and State Complexity of Block Languages Duarte, Guilherme Moreira, Nelma Prigioniero, Luca Reis, Rogério Formal Languages and Automata Theory In this paper, we consider block languages, namely sets of words having the same length, and we propose a new representation for these languages. In particular, given an alphabet of size $k$ and a length $\ell$, a block language can be represented by a bitmap of length $k^\ell$, where each bit indicates whether the corresponding word, according to the lexicographical order, belongs, or not, to the language (bit equal to 1 or 0, respectively). First, we show how to convert bitmaps into deterministic and nondeterministic finite automata, and we prove that the machines are minimal. Then, we give an analysis of the maximum number of states sufficient to accept every block language in the deterministic and nondeterministic case. Finally, we study the deterministic and nondeterministic state complexity of several operations on these languages. Being a subclass of finite languages, the upper bounds of operational state complexity known for finite languages apply for block languages as well. However, in several cases, smaller values were found. |
| title | On the Representation and State Complexity of Block Languages |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2404.11746 |