World's most popular travel blog for travel bloggers.

Transitions triggered by sets of events

, , No Comments
Problem Detail: 

In automata theory books, I always studied examples where a state transition from A to B occurs due to a single event $e$ (say, receiving a particular character). Is it theoretically possible that a transition could be triggered by a set of events, such as receiving any one of some set of characters?

Asked By : New Guy

Answered By : André Souza Lemos

Technically, a transition has to be an atomic event (in the context of formal languages, the reading of a symbol). That said, there are two situations in which you could imagine something different:

1) You could use a set of symbols as an abbreviation of multiple alternative transitions from one state to the other, or a string of symbols as an abbreviation of a sequence of transitions that happen one after the other. In fact, a number of different abbreviations are commonly used when dealing with finite automata on practical situations.

2) You could have a language whose symbols have an internal structure (for instance, they are encodings of sets). Of course, this internal structure should be transparent to the formal treatment of the language.

As with any alternative representation of a formal expression, these variations should be used when their understanding is clear, from definition, or context.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback