To design language recognizer for finite automata.

Problem Statement : To design language recognizer for finite automata.

Theory : We have to design the recognizer for language.

Program taking string x and returning “yes”, if x is in F & returns “no” otherwise.

If the language if finite then this is just a lookup generated by regular expression We will do this for a regular expression given below:

(a/b)(a*/b*)

Finite Automata:

In automata theory, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite state machine—is a finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automaton for each input string. 'Deterministic' refers to the uniqueness of the computation. In search of simplest models to capture the finite state machines, McCulloch and Pitts were among the first researchers to introduce a concept similar to finite automaton in 1943.

The figure at right illustrates a deterministic finite automaton using state diagram. In the automaton, there are three states: S0, S1, and S2 (denoted graphically by circles). The automaton takes finite sequence of 0s and 1s as input. For each state, there is a transition arrow leading out to a next state for both 0 and 1. Upon reading a symbol, a DFA jumps deterministically from a state to another by following the transition arrow. For example, if the automaton is currently in state S0 and current input symbol is 1 then it deterministically jumps to state S1. A DFA has a start state (denoted graphically by an arrow coming in from nowhere) where computations begin, and a set of accept states (denoted graphically by a double circle) which help define when a computation is successful.

A DFA is defined as an abstract mathematical concept, but due to the deterministic nature of a DFA, it is implementable in hardware and software for solving various specific problems. For example, a DFA can model a software that decides whether or not online user-input such as email addresses are valid.

Formal Definition:

A deterministic finite automaton M is a 5-tuple, (Q, Σ, δ, q₀, F), consisting of

• a finite set of states (Q)
• a finite set of input symbols called the alphabet (Σ)
• a transition function (δ : Q × Σ → Q)
• a start state (q₀ ∈ Q)
• a set of accept states (F ⊆ Q)

Let w = a₁a₂ ... a_n be a string over the alphabet Σ. The automaton M accepts the string w if a sequence of states, r₀,r₁, ..., r_n, exists in Q with the following conditions:

1. r₀ = q₀
2. r_i+1 = δ(r_i, a_i+1), for i = 0, ..., n−1
3. r_n ∈ F.

In words, the first condition says that the machine starts in the start state q₀. The second condition says that given each character of string w, the machine will transition from state to state according to the transition function δ. The last condition says that the machine accepts w if the last input of w causes the machine to halt in one of the accepting states. Otherwise, it is said that the automaton rejects the string. The set of strings M accepts is the language recognized by M and this language is denoted by L(M).

A deterministic finite automaton without accept states and without a starting state is known as a transition system or semiautomaton.

Example: The following example is of a DFA M, with a binary alphabet, which requires that the input contains an even number of 0s.

The state diagram for M

M = (Q, Σ, δ, q₀, F) where

1. Q = {S₁, S₂},
2. Σ = {0, 1},
3. q₀ = S₁,
4. F = {S₁}, and
5. δ is defined by the following state transition table:

	0	1
S1	S2	S1
S2	S1	S2

The state S₁ represents that there has been an even number of 0s in the input so far, while S₂ signifies an odd number. A 1 in the input does not change the state of the automaton. When the input ends, the state will show whether the input contained an even number of 0s or not. If the input did contain an even number of 0s, M will finish in state S₁, an accepting state, so the input string will be accepted.

The language recognized by M is the regular language given by the regular expression 1*( 0 (1*) 0 (1*) )*, where "*" is the Kleene star, e.g., 1* denotes any non-negative number (possibly zero) of symbols "1".

Frequently asked questions:

1) What is meant by finite automata?

2)Give Different type of FA's.

3)What is mean by language?

4)What is mean by regular expression?Give Examples of it.