Equivalence of Deterministic and Nondeterministic Epsilon Automata

Michał Trybulec

doi:10.2478/v10037-009-0023-9

.blurhash-client-img { display: none !important; }

Equivalence of Deterministic and Nondeterministic Epsilon Automata

Formalized Mathematics

Volume 17 (2009): Issue 2 (June 2009)

By: Michał Trybulec

Open Access

|Jul 2009

Abstract

Based on concepts introduced in [14], semiautomata and leftlanguages, automata and right-languages, and langauges accepted by automata are defined. The powerset construction is defined for transition systems, semiautomata and automata. Finally, the equivalence of deterministic and nondeterministic epsilon automata is shown.

References

[1] Grzegorz Bancerek. Cardinal numbers., 1(2):377-382, 1990.
Search in Google Scholar
[2] Grzegorz Bancerek. The fundamental properties of natural numbers., 1(1):41-46, 1990.
Search in Google Scholar
[3] Grzegorz Bancerek. The ordinal numbers., 1(1):91-96, 1990.
Search in Google Scholar
[4] Grzegorz Bancerek. Reduction relations., 5(4):469-478, 1996.
Search in Google Scholar
[5] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences., 1(1):107-114, 1990.
Search in Google Scholar
[6] Czesław Byliński. Functions and their basic properties., 1(1):55-65, 1990.
Search in Google Scholar
[7] Czesław Byliński. Functions from a set to a set., 1(1):153-164, 1990.
Search in Google Scholar
[8] Czesław Byliński. Some basic properties of sets., 1(1):47-53, 1990.
Search in Google Scholar
[9] Agata Darmochwał. Finite sets., 1(1):165-167, 1990.
Search in Google Scholar
[10] Karol Pąk. The Catalan numbers. Part II., 14(4):153-159, 2006, doi:10.2478/v10037-006-0019-7.
Open DOI Search in Google Scholar
[11] Andrzej Trybulec. Domains and their Cartesian products., 1(1):115-122, 1990.
Search in Google Scholar
[12] Andrzej Trybulec. Tuples, projections and Cartesian products., 1(1):97-105, 1990.
Search in Google Scholar
[13] Michał Trybulec. Formal languages - concatenation and closure., 15(1):11-15, 2007, doi:10.2478/v10037-007-0002-y.
Open DOI Search in Google Scholar
[14] Michał Trybulec. Labelled state transition systems., 17(2):163-171, 2009, doi: 10.2478/v10037-009-0019-5.
Open DOI Search in Google Scholar
[15] Zinaida Trybulec. Properties of subsets., 1(1):67-71, 1990.
Search in Google Scholar
[16] Tetsuya Tsunetou, Grzegorz Bancerek, and Yatsuka Nakamura. Zero-based finite sequences., 9(4):825-829, 2001.
Search in Google Scholar
[17] Edmund Woronowicz. Relations and their basic properties., 1(1):73-83, 1990.
Search in Google Scholar
[18] Edmund Woronowicz. Relations defined on sets., 1(1):181-186, 1990.
Search in Google Scholar