Nondeterministic Complexity of Operations on Closed and Ideal Languages
We study the nondeterministic state complexity of basic regular operations on the classes of prefix-, suffix-, factor-, and subword-closed regular languages and on the classes of right, left, two-sided, and all-sided ideal regular languages. For the opera
- PDF / 507,242 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 41 Downloads / 214 Views
ction
The nondeterministic state complexity of a regular language L, nsc(L), is the smallest number of states in any nondeterministic finite automaton (NFA) with a single initial state recognizing the language L. The nondeterministic state complexity of a regular operation is defined as the maximal nondeterministic state complexity of languages resulting from the operation, considered as a function of nondeterministic state complexities of the operands. The nondeterministic state complexity of basic operations on regular languages has been investigated in [8,9], and on prefix-free and suffix-free languages in [6,7]. In this paper we continue this research and study the nondeterministic complexity of operations on closed and ideal languages. The (deterministic) state complexity of operations on the classes of closed and ideal languages has ˇ been studied by Brzozowski et al. in [2,3]. Cevorov´ a in [4] examined the state complexity of the square operation on these classes. The class of prefix-closed languages has been investigated in [5]. In this paper we get the tight upper bounds on the nondeterministic state complexity of operations of union, intersection, complementation, concatenation, square, star, and reversal on the classes of prefix-, suffix-, factor-, and subwordclosed languages. We also study the operations on left, right, two-sided and all sided ideals and get tight upper bounds for these classes as well. To prove tightness, we use a fooling set method [1]. Although the gap between a fooling set for a regular language and the size of a minimal NFA for this language may be exponential [10], here this method is successfully used to get tight upper bounds in all the cases. In most cases we describe witness languages over a binary alphabet. P. Mlyn´ arˇcik—Research supported by VEGA grant 2/0084/15. c Springer International Publishing Switzerland 2016 Y.-S. Han and K. Salomaa (Eds.): CIAA 2016, LNCS 9705, pp. 125–137, 2016. DOI: 10.1007/978-3-319-40946-7 11
126
M. Hospod´ ar et al. b q0
b a
q1
b a
...
a q m−1
a
0
a b
1
a b
...
b
n−1
Fig. 1. The DFAs of subword closed languages K and L with nsc(K ∪ L) = m + n + 1.
2
Preliminaries
A language L is prefix (suffix, factor, subword)-closed iff for every w ∈ L every prefix (suffix, factor, subword) of w is in L. Let L be a language over an alphabet Σ. Then we have four classes of ideals. The language L is a right ideal iff L = LΣ ∗ . The language L is a left ideal iff L = Σ ∗ L. The language L is two-sided ideal iff L = Σ ∗ LΣ ∗ . The language L is all-sided ideal iff L = L Σ ∗ , where operation is the shuffle operation. In the paper we investigate the nondeterministic complexity of basic operations on the above mentioned subclasses of regular languages. To prove the minimality of NFAs, we use a fooling set lower-bound technique [1,13]. Definition 1. A set of pairs of strings {(x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )} is called a fooling set for a language L if for all i, j in {1, 2, . . . , n}, (F1) xi yi ∈ L, and / L or xj yi ∈ / L. (F2) if i = j, then xi yj ∈
Data Loading...
