Question

If A is any language, let ${\mathit{A}}_{\frac{\mathbf{1}}{\mathbf{2}}}$− be the set of all first halves of strings in A so that ,

${\mathit{A}}_{\frac{\mathbf{1}}{\mathbf{2}}}\mathbf{-}\mathbf{=}\mathbf{\left\{}\mathit{x}\left|forsomey,\right|\mathit{x}|=|\mathit{y}\mathbf{\right|}\mathit{a}\mathit{n}\mathit{d}\mathit{x}\mathit{y}\mathbf{\in }\mathit{A}\mathbf{\}}\mathbf{.}$

Show that if A is regular, then so is ${\mathit{A}}_{\frac{\mathbf{1}}{\mathbf{2}}}$−

Short answer

Regular language and its deterministic finite machine are shown below.

Step-by-step solution

Regular language.

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.

Regular language or not.

Let $D=\left(Q_A,\Sigma ,{\delta }_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,\Sigma ,\delta ,q,F\right)$such that,

a) $Q=\left(Q_A\times Q_A\right)\cup \left\{q_0\right\},$where$\left(Q_A\times 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\in 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)$\delta$is as follows:

i. $\left(q_A,x\right)\in \delta \left(q_0,\epsilon \right)forx\in 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(\delta A\left(x,a\right),z\right)\in \delta \left(\left(x,y\right),a\right)$for any z such that there exists some c ∈ Σ with $\delta A\left(z,c\right)=y$

. This states that when D advances one step from state x to $\delta 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\in A\}$ is a regular language and deterministic finite machine is possible.