Journal:Informatica
Volume 13, Issue 3 (2002), pp. 299–310
Abstract
In this paper we consider non-deterministic finite Rabin–Scott's automata. We obtain some properties for the basis automaton, which is, like automaton of canonical form, an invariant of a given regular language. We obtain also a new algorithm of constructing the basis automaton for a given regular language.
Journal:Informatica
Volume 11, Issue 4 (2000), pp. 441–454
Abstract
We consider in this paper so called simple bracketed languages having special limitations. They are sometimes used for the definitions of some grammatical structures of programming languages. Generally speaking, these languages are context-free, but not deterministic context-free, i.e., they cannot be defined by deterministic push-down automata. For the simple bracketed languages having special limitations, the equivalence problem is decidable.
We obtain the sufficient conditions for the representation some language by special sequences of simple bracketed languages. We also consider the examples of grammatical structures as the simple bracketed languages. Therefore, we can decide equivalence problem for some grammatical structures of programming languages, and such structures define neither regular, nor deterministic context-free languages.
Journal:Informatica
Volume 11, Issue 4 (2000), pp. 353–370
Abstract
This work is an attempt of generalization of the simple statement about the requirements of commutation of words for the case of languages. In the paper, the necessary condition for commutation of languages are obtained, and in the prefix case the necessary and sufficient conditions are obtained. It is important to note that the considered alphabets and languages can be infinite.
The possibilities of application of the obtained results are shown in the other problems of the theory of formal languages. The boundary problems for the further solution are formulated.