Späť

Zrkadlový obraz na regulárnych jazykoch a popisná zložitosť

Reversal on Regular Languages and Descriptional Complexity

Mgr. Juraj Šebej
Univerzita Pavla Jozefa Šafárika v Košiciach, Prírodovedecká fakulta
Ústav informatiky
Jesenná 5, 040 01 Košice

Abstrakt:
V príspevku sa budeme zaoberať’ nasledujúcim problémom: ktoré hodnoty z rozsahu od log n po 2n môžeme dosiahnuť ako stavovú zložitosť’ zrkadlového obrazu regulárneho jazyka reprezentovaného minimálnym deterministickým n stavovým automatom. Hlavný výsledok, ktorý ukazuje, že celý daný rozsah môže byt’ dosiahnuteľný, pre každé n používa abecedu o veľkosti 2n–2. Ide o značné vylepšenie analogického výsledku z dostupnej literatúry, ktorý používal abecedu o veľkosti 2n. Tiež uvádzame ďalšie získané výsledky nad binárnou abecedou.

Kľúčové slová:
zrkadlový obraz, popisná zložitosť, regulárne jazyky, stavová zložitosť, konečné automaty

Abstract:
We study the problem stated as follows: which values in the range from logn to 2n may be obtained as the state complexity of the reverse of a regular language represented by a minimal deterministic automaton of n states? In the main result of this paper we use an alphabet of size 2n−2 to show that the entire range of complexities may be produced for any n. This considerably improves an analogous result from the literature that uses an alphabet of size 2n.We also provide some partial results for the case of a binary alphabet.

Keywords:
reversal, descriptional complexity, regular languages, state complexity, finite automata

Späť