Here I will describe a strategy or technique to solve some finite state automata problems. This strategy was first taught to us by my Theory of Computation Professor. The term 'Function Automata' is given to me since we use function-like structures in this.
Suppose you are given a language that is a regular set \(L\). So there exists a \(DFA\) for \(L\), \(L_D=(Q,\Sigma,\delta, q_1, F)\) where \(Q\) is the set of states, \(\Sigma\) is the set of alphabets, \(\delta\) is the transition function, \(S\) is the starting state and \(f\) is the set of final states. Now let \(Q=\{q_1,q_2,\dots,q_n\) where \(n\in\mathbb{N}\). Now we will do a kind of subset construction but every new state will have \(n\) states of \(Q\) but they can repeat. So $$(\underbrace{q_1,q_1,\dots,q_1}_{n\text{ times}})$$is a state of the new automata. Now, what is the meaning of these new states? Let \(f=(q_{k_1},q_{k_2},\dots,q_{k_n})\) be a new state where \(q_{k_i}\)'s are not necessary to be different and \(q_{k_i}\in Q\). Then it means on reading some word \(w\) from the state \(q_1\) goes to \(q_{k_1}\), \(q_2\) goes to \(q_{k_2}\) \(\dots\) \(q_n\) goes to \(q_{k_n}\). So basically the new set of states is the set of all functions from \(\{1,\dots, n\} \to \{1,\dots,n\}\). We denote it by \(Q^Q\). So we write $$f(q_1)=q_{k_1}\quad f(q_2)=q_{k_2}\quad\dots\quad f(q_n)=q_{k_n}$$
So we will form transitions on these new elements based on \(\delta\). In most cases, you will be creating \(NFA\) with this. Let the new automata \(N=((Q^Q)^m,\Sigma,\Delta,S',F')\) where \(m\in\mathbb{N}\) depends on question and \((Q^Q)^m=m\) times cartesian product of \(Q^Q\) \(\Delta\) is the transition tuple. So if \((f, a,g)\in \Delta\) that means the automata from state \(f\) on reading \(a\) goes to \(g\) state in the new automata. Also we define \(id\) a special element of \(Q^Q\) which is basically $$id(q_1)=q_{k_1}\quad id(q_2)=q_{k_2}\quad\dots\quad id(q_n)=q_{k_n}$$So \(id=(q_1,\dots,q_n)\). In the new form automata \(S', F'\) depend on what is asked. We will describe some examples.
Now for any letter \(a\in\Sigma\), \(\delta_a(q)=\delta(q,a)\) where \(q\in Q\). Let the new formed Also let \(f=(q_{k_1},q_{k_2},\dots,q_{k_n})\) then for any letter \(a\in\Sigma\) $$\delta_a\circ f=\Big(\delta_a(q_{k_1}),\delta_a(q_{k_2}),\dots, \delta_a(q_{k_n})\Big)$$
Now to show how this technique works I explain by examples.
Question 1: If \(L\) is a regular language then construct \(NFA\) for the set $$\{w\mid ww\in L\}$$
Solution: Let the \(DFA\) of \(L\) is \(L_D=(Q,\Sigma,\delta, q_1, F)\). We will create the function automata \(N=(Q^Q,\Sigma,\Delta,S',F')\) where \(S'=id\). Now I told you \(f(q_1)=q_{k_i}\) means \(q_1\) goes to \(q_{k_i}\) on reading some word \(w\). So \(f\circ f(q_1)=q_{k_j}\) means on reading \(w\) \(q_1\to q_{k_i}\) then \(q_{k_i}\to q_{k_j}\) therefore $$q_1\underset{w}{\to} q_{k_i}\underset{w}{\to}q_{k_j} \iff q\underset{ww}{\to}q_{k_j}$$So if \(f\circ f(q_1)\in F\) that means if \(q_{k_j}\in F\). Hence for any \(f\in F'\) if there exists a word \(w\) such that \(id\underset{w}{\to}f\) then \(\hat{\delta}(q_1,w)\in F\) and similarly for any \(w\), if \(ww\in L\) then take \(f=(\hat{\delta}(q_1,w), \hat{\delta}(q_2,w),\dots, \hat{\delta}(q_n,w))\). Now \(f\in F'\). Hence \(id\underset{w}{\to}f\). Therefore we set \(F'=\{f\in Q^Q\mid f\circ f(q_1)\in F\}\). All is left is to define \(\Delta\). Take$$\Delta=\{(f,a,\delta_a\circ f)\mid \forall\ f\in Q^Q,\ \forall\ a\in \Sigma\}$$
Now I think you got a little hang of the use of it. Let's do another example but a tough one.
Question 2: If \(L\) is a regular language then construct \(NFA\) for the set $$\{yx\mid xy\in L\}$$
Solution: Let the \(DFA\) of \(L\) is \(L_D=(Q,\Sigma,\delta, q_1, F)\). We will create the function automata \(N=(Q^Q\times Q^Q\times \{0,1\},\Sigma,\Delta,S',F')\). Here since two subwords \(x,y\) are involved and they are independent of each other, we will take two functions, \(g,f\) and process with that. Here we will take \(S'=(id, id)\). For any \((g,f)\in Q^Q\times Q^Q\), \(g\) denotes the reading of \(y\) and \(f\) denotes the reading of \(x\). So \(f(q_1)=q_{k_i}\) means \(q_1\) goes to \(q_{k_i}\) on reading some word \(x\). Then \(g(q_{k_i})=q_{k_j}\) means \(q_{k_i}\) goes to \(q_{k_j}\) on reading some word \(y\). Hence \(g\circ f(q_1)=q_{k_j}\) means \(q_1\) first reads \(x\) and goes to \(q_{k_i}\) and then reads \(y\) and goes from there to \(q_{k_j}\).$$q_1\underset{x}{\to}q_{k_i}\underset{y}{\to}q_{k_j}\iff q_1\underset{xy}{\to}q_{k_j}$$ So if \(g\circ f(q_i)\in F\) that means \(q_1\) goes to final state \(q_{k_j}\) on reading word \(xy\). Hence our final state will be \(F'=\{(g,f,1)\mid f,g\in Q^Q,\ g\circ f(q_1)\in F\}\). But what about the transitions. The reason for using \(\{0,1\}\)comes now. See once you complete reading \(y\) you can not read \(y\) anymore you have to read \(x\). So when transitions of \(g\) are complete you will move to transition \(f\) and that's it. That's where \(\{0,1\}\) comes. When you are reading \(y\) you are in \(0\) and when you are reading \(x\) you are in \(1\). So can go from 0 to 1 but not 1 to 0. And because of this, we took elements \((g,f,1)\) for \(F'\) to indicate that when you reach the final state you are reading \(x\). So $$\Delta=\left\{\left.\begin{matrix}\big((g,f,0),a,(\delta_a\circ g,f,0)\big),\\ \big((g,f,0),a,(\delta_a\circ g,f,1)\big), \\ \big((g,f,1),a,( g,\delta_a\circ f,1)\big)\end{matrix} \right|\ \forall\ f,g\in Q^Q, \forall\ a\in\Sigma\right\}$$
Now you get how you can use this technique in solving complex problems. And you can use multiple functions in one automata. Now we will see another problem with more subwords.
Question 3: If \(L\) is a regular language then construct \(NFA\) for the set $$\{xzy\mid xyzx\in L\}$$
Solution: Let the \(DFA\) of \(L\) is \(L_D=(Q,\Sigma,\delta, q_1, F)\). We will create the function automata \(N=(Q^Q\times Q^Q\times Q^Q\times \{0,1,2\},\Sigma,\Delta,S',F')\). Naturally we will take \(S'=(id,id,id)\). Here same for any \((f,h,g)\in Q^Q\times Q^Q\times Q^Q\), \(f,g,h\) are for reading \(x,y,z\) respectively $$f\circ h\circ g\circ f(q_1)=q_{k_4}\iff q_1\overset{f}{\underset{x}{\to}}q_{k_1}\overset{g}{\underset{y}{\to}}q_{k_2} \overset{h}{\underset{z}{\to}} q_{k_3}\overset{f}{\underset{x}{\to}}q_{k_4}\iff q_1\underset{xyzx}{\longrightarrow}q_{k_4}$$We took the set \(\{0,1,2\}\) for same reason as the previous question. 0 indicates you are reading \(x\), 1 indicates you are reading \(z\) and 2 indicates you are reading \(y\). So naturally $$F'=\{(f,h,g,2)\mid f,g,h\in Q^Q,\ f\circ h\circ g\circ f(q_1)\in F\}$$And now you can guess what will be the set \(\Delta\). $$\Delta=\left\{\left.\begin{matrix}\big((f,h,g,0),a,(\delta_a\circ f,h,g,0)\big),\\ \big((f,h,g,0),a,(\delta_a\circ f,h,g,1)\big), \\\big((f,h,g,1),a,(f,\delta_a\circ h,g,1)\big),\\\big((f,h,g,1),a,(f,\delta_a\circ h,g,2)\big),\\ \big((f,h,g,2),a,(f,h,\delta_a\circ g,2)\big),\end{matrix}\right|\ \forall\ f,g,h\in Q^Q, \forall\ a\in\Sigma\right\}$$
Till now you see we are taking \(S'=id\) or \((id,id\) or \(id,id,id)\) but that does not mean starting state will be always the cartesian product of \(id\). There is a specific reason why we took that.
Question 4: If \(L\) is a regular language then construct \(NFA\) for the set $$\{x\mid xyx\in L\}$$
Solution: Let the \(DFA\) of \(L\) is \(L_D=(Q,\Sigma,\delta, q_1, F)\). Since two independent subwords are involved we will create the function automata \(N=(Q^Q\times Q^Q ,\Sigma,\Delta,S',F')\). Now we can pretty easily guess that the final set will be $$F'=\{(f,g)\mid f\in Q^Q, f\circ g\circ f(q_1)\in F\}$$ Notice that the set \(\{x\mid xyx\in L\}\) the words don't have the part \(y\). So it doesn't matter if we start from \((id,id)\) or not. We can start from anywhere for the \(y\) part and then keep progressing for the function for \(x\). So for any \((f,g)\) [where \(f\) is for \(x\) and \(g\) is for \(y\)] it does not matter if we progress \(g\) or not. For any \(f\in Q^Q\) we take all such pairs and then check if \(f\circ g\circ f(q_1)\in F\) is satisfied or not. So here we take $$S'=\{(id,g)\mid \forall\ g\in Q^Q\}$$And we define \(\Delta\) $$\Delta=\{((f,g),a,(\delta_a\circ f,g))\mid \forall\ f\in Q^Q,\ \forall\ a\in \Sigma\}$$
Now you get what is the idea behind choosing \(S'\). Yes if any word \(w\in L\) is partitioned into \(k\) parts and \(l\) of them are taken in some order for constructing the new set of words then for the parts which is common in both \(w\) and newly formed word form it we take \(id\) and the parts of \(w\) which aren't taken in the newly formed word we take the whole set \(Q^Q\) and in transitions we don't move at all for the parts which is not in the new words. So for example for the set $$\{x_1x_3x_4\mid x_1x_2x_1x_4x_3x_5\in L\}$$ where \(L\) is regular then take for starting state in the function automata \(\{id\}\times Q^Q\times\{id\}\times\{id\}\times Q^Q\times \{0,1,2\}\) [Though the \(\{0,1,2,3,4\}\) is when it is necessary. Like in Question 1 or 4 we didn't need it but in Question 2,3 we needed it] and for final state \(F'=\{(f_1,f_2,f_3,f_4,f_5,2)\mid f_5\circ f_3\circ f_4\circ f_1\circ f_2\circ f_1(q_1)\in F\}\) and the transitions will be independent of the \(f_2,f_5\).
So now I think you have learned how to use this technique for solving such finite state automata problems.
Comments
Post a Comment