On generating a random deterministic finite automaton as well as its failure equivalent

M. Nxumalo, D.G. Kourie, L.G.W.A. Cleophas, B.W. Watson

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

Abstract

An algorithm is proposed that constructs a failure deterministic finite automaton in lockstep with the construction of a languageequivalent deterministic finite automaton. The states of both automata are assumed to be predefined and the failure deterministic finite automaton's symbol and failure transitions are randomised. It is guaranteed that the latter remains free of divergent failure cycles. The benefits are explained of using this algorithm to produce input data for testing algorithms that produce a language-equivalent FDFA from an arbitrary DFA.

Original languageEnglish
Title of host publicationProceedings of Russian and South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015), November 30 - December 5, 2015, Stellenbosch, South Africa
PublisherCEUR-WS.org
Pages47-57
Number of pages11
Volume1552
Publication statusPublished - 2015
Event1st Russian-South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015), November 30-December 5, 2015, Stellenbosch, South Africa - Stellenbosch, South Africa
Duration: 30 Nov 20155 Dec 2015

Workshop

Workshop1st Russian-South African Workshop on Knowledge Discovery Techniques Based on Formal Concept Analysis (RuZA 2015), November 30-December 5, 2015, Stellenbosch, South Africa
Abbreviated titleRuZA 2015
CountrySouth Africa
CityStellenbosch
Period30/11/155/12/15

Keywords

  • Random Failure Deterministic Finite Automaton

Fingerprint Dive into the research topics of 'On generating a random deterministic finite automaton as well as its failure equivalent'. Together they form a unique fingerprint.

Cite this