Search

Your search keyword '"Powerset construction"' showing total 3 results
Start Over Descriptor "Powerset construction" Journal international journal of computer applications
3 results on '"Powerset construction"'

1. Algorithm to Generate DFA for AND-operator in Regular Expression

Author

Mirzakhmet Syzdykov

Subjects
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Finite-state machine, Deterministic finite automaton, Regular language, Computer science, Intersection (set theory), Powerset construction, Pattern recognition (psychology), Regular expression, Bitwise operation, Algorithm, Computer Science::Formal Languages and Automata Theory
Abstract

For the past time a number of algorithms were presented to produce a deterministic finite automaton (DFA) for the regular expression. These algorithms could be divided into what they used as an initial data from which to produce DFA. The method to produce DFA from non-deterministic finite automaton (NFA) by a subset construction could be generalized for extended regular expressions, including intersection, negation and subtraction of the regular languages. In this article the modified algorithm of subset construction is presented; this algorithm produces a unigram DFA for the regular expression with extensions (specifically AND-operator). General Terms Pattern Recognition; Finite Automata; Algorithms.

Published
2015

2. On Cardinality of the Group of Weak Fuzzy Automaton Isomorphisms

Author

S. R. Chaudhari and S. S. Dhure

Subjects
Discrete mathematics, Block cellular automaton, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Mathematics::General Mathematics, Computer science, Powerset construction, Continuous automaton, Timed automaton, Pushdown automaton, Büchi automaton, Nonlinear Sciences::Cellular Automata and Lattice Gases, Reversible cellular automaton, Deterministic pushdown automaton, Nondeterministic finite automaton with ε-moves, ComputingMethodologies_PATTERNRECOGNITION, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Elementary cellular automaton, Deterministic automaton, Probabilistic automaton, Two-way deterministic finite automaton, ComputingMethodologies_GENERAL, Nondeterministic finite automaton, Isomorphism, Algorithm, Computer Science::Formal Languages and Automata Theory
Abstract

Recent studies on fuzzy automata are influenced by algebraic techniques to tackle issues like reduction, minimization and their languages. Fuzzy automaton homomorphism is one such majorally discussed technique. This paper is concerned with the group of (weak) fuzzy automaton automorphisms and constructions of all (weak) fuzzy automaton automorphisms over arbitrary fuzzy automaton. It is shown that (1) every arbitrary fuzzy automaton is decomposed into distinct primaries, (2) primaries are maximal singly generated fuzzy automata and (3) every weak fuzzy automaton homomorphism on an arbitrary fuzzy automaton is uniquely determined into weak fuzzy automaton homomorphisms on all its primaries. Therefore, the discussion begun over strongly connected fuzzy automaton and continue constructions as well as characterizations of (weak) fuzzy automaton homomorphisms, isomorphisms, endomorphisms and automorphisms sequentially over perfect fuzzy automaton, singly generated fuzzy automaton and primaries of fuzzy automaton. Finally, it is obtained that the group of weak fuzzy automaton automorphisms and its cardinality over arbitrary fuzzy automaton.

Published
2013

3. A Structural Construction of a Deterministic Position Automaton

Author

N. Murugesan and O. V. Shanmuga Sundaram

Subjects
Computer science, Position (vector), Deterministic automaton, Powerset construction, Two-way deterministic finite automaton, Nondeterministic finite automaton, Regular expression, Algorithm, Computer Science::Formal Languages and Automata Theory, Automaton
Abstract

Every regular expression can be transformed into a Nondeterministic Finite Automaton (NFA) with or without  transitions. A well known algorithm called subset construction technique is used for conversion of NFA into DFA. In this paper, initially, the construction of the position automaton is given for the same. Also, the algorithm to convert this Position Automaton into DFA using subset construction technique is discussed. AMS MSC2010 Certification: 68Q45, 68Q70

Published
2013

Catalog

Books, media, physical & digital resources
See catalog results