The validation of a string for its membership in a language are handled by automata.

An automaton acts as a acceptor of a string for a given language

This is an example for an automaton which accepts **all strings containing at least one 'a'**.

These circles are known as states. So **X** and **Y** are states.

Circle with dual boundary (here **Y**) is final state and one with unmarked arrow is initial state(here **X**).

Consider the string "baba",

Initially we are at **X**, on seeing first alphabet **'b'** the automaton **loop back to X itself**( Edge with alphabet 'b' point to X itself).

On seeing next alphabet **'a'**, the state transition happens and reaches at new state **Y**.

Once we reaches at state **Y**, both 'a' and 'b' loop back to the same state.

So the string "baba" finally reaches as state **Y**

Since the **Y** is the final state of this automaton, we can conclude that the sting "baba" belongs to the language represented by the given automaton.

All finite automata are classified as follows :

- Automata with output
- Moore Machine
- Mealy Machine

- Automata without output
- Deterministic Finite Automata (DFA)
- Non-deterministic Finite Automata (NFA)
- Epsilon NFA (ε-NFA)

We will discuss about each of of them in detail in upcoming posts.

## Comments

## Post a Comment