91Ó°ÊÓ

A language is regular if it can be expressed in terms of regular expression.A regular expression can also be described as a sequence of pattern that defines a string. Regular expressions are used to match character combinations in strings.

Let $D=\left(Q_A,\mathrm{Î\pounds },{\mathrm{δ}}_A,q_A,F_A\right)$be a DFA recognizing We shall construct an NFA that recognizes The idea is that, when we have processed the ith input characters,N is able to keep track both the state of D when processed the string so far, and the possible states which can reach some accept state of D in i steps. Then, a string is accepted by N when the current state is in one of these possible states. Formally,

Let $N=\left(Q,\mathrm{Î\pounds },\mathrm{δ},q,F\right)$such that,

a) $Q=\left(Q_A×Q_A\right)∪\left\{q_0\right\},$where$\left(Q_A×Q_A\right)$keeps track of the current state ofD , and the state that can reach an accept state of D in i steps, where i is the length of the input string processed so far. In addition, we create a state$q_0$, which denotes the state when nothing is read.

(b) $q=q_0.$

(c) $F=\left\{\left(x,x\right)\right|x∈Q_A\},$which states that a string is accepted when the current state of D is at x , and $xisi$steps from some accept state of D, where i is the length of the input string processed so far.

(d)$\mathrm{δ}$is as follows:

i. $\left(q_A,x\right)∈\mathrm{δ}\left(q_0,\mathrm{Î\mu }\right)forx∈F_A$, which states that without reading anything, we make D to start at qA, and keep track that is zero steps from some accept state of D .

Ii $.\left(\mathrm{δ}A\left(x,a\right),z\right)∈\mathrm{δ}\left(\left(x,y\right),a\right)$for any z such that there exists some c ∈ Σ with $\mathrm{δ}A\left(z,c\right)=y$

. This states that when D advances one step from state x to $\mathrm{δ}A\left(x,a\right),$we update the state y to some state z which is one more step further from the accept state of D.

Hence, $A_{\frac{1}{2}}-=\left\{x\left|forsomey,\right|x\left|=\right|y\right|andxy∈A\}$ is a regular language and deterministic finite machine is possible.