PlanetMath: semiautomaton

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

semiautomaton

(Definition)

A semiautomaton is basically an automaton without designated sets of starting and final states. Formally, a semiautomaton is a triple $(S,\Sigma,\delta)$ where

is a non-empty set whose elements are called states
$\Sigma$ is a non-empty set of symbols, and
$\delta$ is a transition function that assigns each pair $(s,\alpha)$ of state and symbol $\alpha$ a subset $\delta(s,\alpha)$ of states in .

A semiautomaton is said to be deterministic if $\delta(s,\alpha)$ is a singleton for each $(s,\alpha)\in S\times \Sigma$ . In otherwords, $\delta$ is a function from $S\times \Sigma$ to in a deterministic semiautomaton. Otherwise, it is non-deterministic.

What we would like to do is to extend the transition function $\delta$ so it is applicable to all finite strings over $\Sigma$ . This is done in two steps: extend the transition function $\delta: S\times \Sigma\to P(S)$ to a function $\delta_1: P(S)\times \Sigma \to P(S)$ as follows:

$\displaystyle \delta_1(Q,\alpha):=\bigcup_{s\in Q} \delta(s,\alpha),$

and $\delta_1$ can be further extended to a function $\delta_2: P(S)\times \Sigma^*\to P(S)$ recursively, given by

$\begin{displaymath} % latex2html id marker 330\delta_2(Q,a):= \left\{ \begin{a... ...a$\ with $b\in \Sigma^*,\alpha\in \Sigma.$} \end{array}\right. \end{displaymath}$

Without causing any confusion, we may identify $\delta_1$ and $\delta_2$ with $\delta$ . Basically, when a string $a=\alpha_1\alpha_2\cdots \alpha_n$ is fed into a semiautomaton

that is in state

, $\delta$ takes the first symbol $\alpha_1$ and computes the next states $\delta(s,\alpha_1)$ . Then it takes the next symbol $\alpha_2$ and computes all the next states $\delta(\delta(q,\alpha_1),\alpha_2)$ . It continues to do this until the last symbol $\alpha_n$ has been fed, and the next states corresponding to

is $\delta(s,a)$ . From the recursive definition above, it is not hard to see that

$\displaystyle \delta(Q,ab)=\delta(\delta(Q,a),b)$

for any $a,b\in \Sigma^*,$ as the concatenation operation is associative.

In the case of a deterministic semiautomaton, $\delta$ is just a function $S\times \Sigma^*$ to .

Bibliography

1: A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).
2: M. Ito, Algebraic Theory of Automata and Languages, World Scientific (2004).

"semiautomaton" is owned by CWoo.

(view preamble)

See Also: automaton

Also defines:

semiautomata

Log in to rate this entry.
(view current ratings)

Cross-references: associative, operation, concatenation, recursive, strings, finite, function, singleton, subset, transition function, states, final states, automaton
There is 1 reference to this entry.

This is version 8 of semiautomaton, born on 2008-01-30, modified 2008-05-11.
Object id is 10229, canonical name is Semiautomaton.
Accessed 377 times total.

Classification:

AMS MSC:	68Q45 (Computer science :: Theory of computing :: Formal languages and automata)
	03D05 (Mathematical logic and foundations :: Computability and recursion theory :: Automata and formal grammars in connection with logical questions)
	20M35 (Group theory and generalizations :: Semigroups :: Semigroups in automata theory, linguistics, etc.)
	68Q70 (Computer science :: Theory of computing :: Algebraic theory of languages and automata)

Pending Errata and Addenda

None.

Discussion

forum policy

No messages.

Interact