ROBOTS OF BATTERY:

The student will understand the fundamentación of free languages of context. He will learn to construct free grammars of context that define a language and its annotation BNF, besides to learn to use the battery robots.

3.1 ROBOTS OF BATTERY Or PUSH - DOWN (PDA).

A robot of battery or Push-Down is a robot who counts on a mechanism that allows limitless storage and operates as a battery. The battery robot (PDA of their abbreviations in English Push-Down is brief Robot) has a tape of entrance, a finite control and a battery. The battery is a chain of symbols of some alphabet. The symbol that is more to the left considers because it is in the "top".

The movements will be of two types. In the first type of movement an entrance symbol is used. Depending on the symbol of entrance, the symbol of the top and the state of finite control, a number of alternatives is possible.

Each alternative consists of a later state for the finite control and a chain (possibly empty) of symbols, to replace the symbol that is in the top of the battery.

The second type of movement known like movement he is similar to first, unless the entrance symbol is not used and the head of the entrance does not advance after the movement.

Two ways exist to accept a language by a piling up robot. First it consists of defining the language accepted like the set of all the entrances for which a succession of movements causes that the battery robot drains his battery. The second way is designating to some states as final states and we defined the language accepted like the set of all the entrances for which some selection of movement causes that the battery robot accese a final state.

A robot of battery M is a system (Q, S , G , d , q₀, Z₀, F), in where:

Q is a finite set of states.

S entrance alphabet is the called alphabet.

G t is the alphabet, known as battery alphabet.

q₀_ÎQ, is the initial state.

Z₀ Î G initial symbol is the called symbol.

F Í Q is the set of final states.

d it is a transformation of Q x (S È a {e }) x G in finite subgroups Q x G *.

It is M=(Q, S , G , d , q₀, Z₀, F) a battery robot. The language accepted by M is denoted by L(M) and is set L(M) = {wÎ S *½ ( q₀, w, Z₀) * (p, e , u ) for pÎ F and uÎ G *}.

Note: * it is used to denote the movements with an arbitrary number of steps, where * it indicates "zero or more steps". Obsérvese that the acceptance requires that M moves to a final state when the chain w is exhausted. M can finish or not with the empty battery. (Nevertheless, it obsérvese that when the empty battery the PDA is due to stop, since all the transitions require a battery symbol).

The following example represents a battery robot that accepts to { wcwR|w? (0+1) * } by means of an exhaustion of battery M=(Q, S , G , d , q₀, Z₀, F).. Where:

Q = {q₁, q₂} q₀= q₁

S = {0, 1, C} Z₀= R

G = {R, B, G} F = Æ

and d t is defined by:

d (q₁, 0, R) = {(q₁, BR)}
d (q₁, 0, B) = {(q₁, BB)}
d (q₁, 0, G) = {(q₁, BG)}
d (q₁, c, R) = {(q₂, R)}
d (q₁, c, B) = {(q₂, B)}
d (q₁, c, G) = {(q₂, G)}
d (q₂, 0, B) = {(q₂, e )}
d (q₂, e , R) = {(q₂, e )}
d (q₁, 1, R) = {(q₁, GR)}

d (q₁, 1, B) = {(q₁, GB)}
d (q₁, 1, G) = {(q₁, GG)}
d (q₂, 1, G) = {(q₂, e )}

Analyzing the chain 0Ç10 using the previous PDA obtains the following thing:

(q1, 0Ç10, R) by rule 1→ (q1, Ç10, BR) by rule 10→ (q1, C10, GBR) by rule 6→ (q2, 10, GBR) by rule 12→ (q2, 0, BR) by rule 7→ (q2? R) by rule 8→ (q2, and the battery

Robots of Battery .

The battery robots are machines that allow us to accept free languages of context. The battery robots are finite machines that have a memory that gives the capacity them "to remember". This way it is possible to recognize languages of the type ⁱb ⁱ|i > = 0, in which it is needed to know to whatever a’s has the word to determine if the number of b’s is equal.

Classification of Robots Push Down

Contracted battery robots
Ascending contracted battery robots
Restricted logical battery robots
Linear robots of indices
Robots with two batteries

Contracted battery robots

In which the main structure of storage constitutes a battery of batteries. Next to the classic definition a new formulation appears in which the control of finite state is eliminated and the form of the transitions is simplified to the time that stays the expressive power. This new formulation allows to design a technique of tabulation for the efficient execution of the diverse schemes of compilation for grammars of adjunción of trees and linear grammars of indices.

Ascending contracted battery robots

They constitute the ascending contracted battery robots. In this chapter a formal definition of such is made, something that had not been obtained until the moment. The elimination of the control of finite state allows to simplify the form of the transitions, which facilitates the definition of a technique of tabulation for this model of robot.

Restricted logical battery robots

The linear grammars of indices constitute a specific type of grammars of defined clauses in which the predicates have an only argument in form of battery of indices. We took advantage of this characteristic to define a restricted version of the logical battery robots adapted to the treatment of this type of grammars and of the grammars of adjunción of trees. Depending on the form of the allowed transitions, we can distinguish three types different from robot, one that allow to the ascending analysis of the indices or adjunciones, other that the descendent analysis allows and other that allow mixed strategies. In both last cases it is precise to establish restrictions in the combination of the transitions to guarantee that these robots exactly accept the class of the languages of adjunción of trees. Schemes of compilation and techniques of tabulation for the three types of robot appear.

Linear robots of indices

The linear robots of indices, that use the same structure of storage that restricted the logical robots to battery but with a game different from transitions. We distinguished three types different from robot: the linear robots of indices oriented to the right for strategies in which the batteries of indices are evaluated of ascending way, the linear robots of indices oriented to the left in which the batteries evaluate of descendent way and the linear robots of strongly directed indices that allow to define mixed strategies of analysis for the treatment of the batteries of indices.

Robots with two batteries

He decides himself on a model of robot with a new structure of storage. The battery of the traditional battery robots is preserved, to which it accompanies an auxiliary battery whose content restricts the set of applicable transitions a little while is given. The robots with two strongly directed batteries allow to define arbitrary schemes of compilation for grammars of adjunción of trees and linear grammars of indices. On the other hand, the robots with two ascending batteries only allow to describe compilation schemes that incorporate ascending strategies in the referring thing to the treatment of the adjunciones and the batteries of indices. The tabulation techniques appear that allow an efficient execution of both models of robot.

The typical operation of a robot pushdown.

For example, the following robot of battery recognizes L(G) = { wcw ^R|w E (0+1) * }, is to say palíndromes in (0 + 1) * whose intermediate point is noticeable with a special character c:

M = ({ q1, q2 }, { 0.1 }, { RBG }, d , q1, R, q )

Where d it is worth:

Figure 3,4,1. - Description of the value of d .

Robots of battery not-determinists

The battery robots not-determinists agree with their homologous ones of safe battery in which its transition is not properly a function. Here it is had transition is a subgroup $$t \subset (Q \times T \times V) \times (Q \times V^*)$ .

Example: The language of palíndromas without central mark

$\begin{displaymath}L = \{ \mbox{\bf x} \in (0 + 1)^* \vert \mbox{\bf x} = \mbox{\rm reverso}(\mbox{\bf x}) \}\end{displaymath}$

not-determinist is recognized by battery robots who works in agreement with the sigiente procedure:

Advancing to the right, each symbol is stored firstly and when `` is created '' to be to half, each symbol read with the top of the battery is compared. If they agree, it is continued. In another case an error is marked.

The not-determinism of the robot is in which it does not need in what moment will happen to the state to desempilar. It journeys to that one of indetermine way.

Determinist robots of battery

A robot of determinist battery is a battery robot

$\begin{displaymath}\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,F)\end{displaymath}$

where the two properties are fulfilled following:

For any pair (been, tope_de_la_pila) the robot has itself either has defined the transition corresponding to the word of empty entrance or has it defined in symbols of the entrance alphabet, and
for any terceta (been, s , tope_de_la_pila), the corresponding transition contains, at the most, a pair (nuevo_estado, tope_de_la_pila).

In symbols,

$\begin{displaymath}\begin{array}{lrcl} \forall (q,Y)\in Q\times \mbox{\it AlfP\... ...ox{\it tran\/}(q,\mbox{\it nil\/},Y)\right)\leq 1 \end{array}\end{displaymath}$

Be $\mbox{\it AutP\/}=(Q, \mbox{\it Ent\/}, \mbox{\it AlfP\/}, \mbox{\it tran\/}, q_0, X, F)$ a robot of determinist battery. In agreement with the Vista construction to obtain the free grammar of context of a given robot of battery, we will have them productions of the corresponding grammar have to be the following ones:

$\forall q\in Q: \ S\rightarrow [ q_0, X, q]$

$\forall q\in Q, e\in\mbox{\it Ent\/}, Y\in\mbox{\it AlfP\/}:$ $\{(q', y_1y_2\cdots Y_m)\}=\mbox{\it tran\/}(q, and, Y) \ \Rightarrow$

$\begin{displaymath}[q,Y,q^{(m+1)}]\rightarrow e[q',Y_1,q^{(2)}][q^{(2)},Y_2,q^{(3)}]\cdots[q^{(m)},Y_m,q^{(m+1)}]\end{displaymath}$

for any selections of the states $$q^{(2)}, \ldots, q^{(m)}, q^{(m+1)}, \in Q$ .

$\forall q\in Q, e\in\mbox{\it Ent\/}, Y\in\mbox{\it AlfP\/}:$ $\{(q', y_1y_2\cdots Y_m)\}=\mbox{\it tran\/}(q, \mbox{\it nil\/}, and) \ \Rightarrow$

$\begin{displaymath}[q,Y,q^{(m+1)}]\rightarrow [q',Y_1,q^{(2)}][q^{(2)},Y_2,q^{(3)}]\cdots[q^{(m)},Y_m,q^{(m+1)}]\end{displaymath}$

for any selections of the states $$q^{(2)}, \ldots, q^{(m)}, q^{(m+1)}, q^{(m+2)}\in Q$ .

$\forall q\in Q, e\in\mbox{\it Ent\/}, Y\in\mbox{\it AlfP\/}:$ $\{(q', \mbox{\it nil\/})\}=\mbox{\it tran\/}(q, and, Y) \ \Rightarrow \ \left([q, and, q']\rightarrow e\right)$ .

$\forall q\in Q, Y\in\mbox{\it AlfP\/}:$ $\{(q', \mbox{\it nil\/})\}=\mbox{\it tran\/}(q, \mbox{\it nil\/}, and) \ \Rightarrow \ \left([q, and, q']\rightarrow \mbox{\it nil\/}\right)$ .

In this case, if for a pair $(q, y)\in Q\times\mbox{\it AlfP\/}$ productions in agreement with then rule 3 were generated will not be generated no with rule 2. Similar, if one with the 5 were generated, no with the 4 will be generarará. From it is here that any language recognized by a robot of determinist battery has to be generated by a free grammar of context whose productions are of the form

$\begin{eqnarray*}A &\rightarrow& \sigma_1A_1 \cdots \sigma_{k-1}A_{k-1} \sigma_{... ...bien }\\ A &\rightarrow& e,\hspace{2ex} e\in\mbox{\it AlfP\/} \end{eqnarray*}$

LINEAR ROBOTS:

The student will learn to use the linear robots fugitives, will construct sensible grammars to the context and will understand his application in the natural languages.

LINEAR ROBOTS (LBA).

A limited linear robot (LBA of its abbreviations in English Linear-Bounded Robot) is a machine of nondeterminística Turing (for greater understanding of the subject she sees chapter V of Machines of Turing) that satisfies following the two conditions.

The linear robots are determinist robots of battery who throughout their computation only do `` change of turn ' '. In general, this means that all computation consists of a procedure of empilar consecutively later to happen to desempilar:

1. The alphabet of tape entrance includes two symbols: < and >, the signallers of left and right end, respectively.

2. The LBA does not have movements to the left of < or the right of >, nor can replace the symbols < and >.

We will linearly define an annotated robot like a machine of Turing nondeterminist M=(Q, S , G , d , q₀, B, F), in which the tape alphabet contains two special symbols < and >. M begins with the configuration (q₁, £ w>) (where q1 is the initial state of M). It is not allowed that M replaces the symbols < or >, nor that moves its head to the left of < or the right of >, with which, the LBA must make their computation in the only cells of the tape which originally they were occupied by the entrance chain. For example, we consider the LBA defined by:

Q ={q₁, q₂}, S ={a, b}, G ={a, b, <, >}, F ={q₂}, q₀ =q₁and d dice by:

d (q₁, <) = (q₁, <, R)

d (q₁, a) = (q₁, b, R)

d (q₁, b) = (q₁, a, R)

d (q₁, >) = (q₁, >, S), where S means "to remain", is to say not to move the read/write head. This LBA complements their chains of entrance vice versa turning a?s b?s and. Obsérvese that, although can recognize and to work on the symbols < and >, cannot replace them or move beyond them. Let us suppose that a LBA always begins with their head located on the symbol <.

Example: Let us consider the language of palíndromas with a central mark:

$\begin{displaymath}L=\{\mbox{\bf y}M\mbox{\bf x}\vert\mbox{\bf x}\in (0+1)^*,\mbox{\bf y}=\mbox{\it reverso\/}(\mbox{\bf x})\}.\end{displaymath}$

Let us consider the battery robot whose components are the following ones:

$\begin{displaymath}\begin{array}{lcl} Q = \{\mbox{\rm Meter}, \mbox{\rm Sacar},... ...ox{\rm Meter} &:& \mbox{\rm s\'\i mbolo inicial}, \end{array}\end{displaymath}$

and whose function of transition acts as it follows,

$\begin{displaymath}t:\begin{array}{lcll} (\mbox{\rm Meter},0,y) &\mapsto& (\mbo... ...},\mbox{\it nil\/}) &\mbox{\rm estado de \'exito,} \end{array}\end{displaymath}$

where $$y\in V$ and b is the white symbol `` ' '. In any other instance of t , this one it will journey to the failure state. It is clear that this robot of battery recognizes language L

FINITE ROBOTS

Objective: The student will know the fundamentación the finite robots, will learn to construct determinísticos finite robots, nondeterminísticos robots and nondeterminísticos robots with movement? and he will relate these robots to regular expressions.

2,1, FINITE ROBOTS DETERMINÍSTICOS (DFA?S).

The characteristics of the determinísticos finite robots are:

1. A finite set of states and a set of transitions of state to state, that occur on symbols of entrance taken from an alphabet ∑ .

2. For each symbol of entrance a transition from each state exists exactly (possibly of return to the same state).

3. A state, generally denoted like q0 is the initial state, in which the robot begins.

4. Some states (perhaps none) are designated as final or of acceptance.

A determinístico finite robot is a villa tupla (Q, S , d , q₀, F) where:

Q is a finite set of states.

∑ a finite alphabet of entrance.

q0 element of Q, the initial state.

FÍ Q the set of final states or acceptance.

d it is the function d Q x ∑ → Q that determines the only following state for the pair (q₁, s ) corresponding to the present state q1 and the entrance s .

The term determinístico finite robot is brief generally like DFA of its abbreviations in English Deterministic Finite Automaton. We will use M = (Q,  , q₀, F,  ) to indicate the set of states, the alphabet, the initial state, the set of final states and the function associated with DFA M.

A diagram can be constructed so that it helps to determine the different members or chains from the language. Such diagram has the form of a graph directed with added information, and transition diagram is called. The nodes of the graph correspond to the states of the DFA and they are used to indicate, then, until what place analyzed the chain. Generally q0 is the initial state, marking with an arrow (→ ), the beginning of the robot; some states are designated like end or acceptance indicated by a double circle. The symbols of the alphabet are the labels of the arcs of the graph. If when has been treated the chain in its totality is finished in a state of then acceptance the chain it is accepted by the language. If M is a AFD, then the language accepted by M is L(M)={ w Î S *½ w is accepted by M }. Therefore, L(M) is the set of chains that cause that M happens of their initial state to an acceptance state. Example: The language that accepts the DFA this formed by all the chains on the alphabet ∑ = { a, b }, as long as they finish with a.

Q = {q₀, q₁}, S = {a, b}, q₀ = q₀ , F = {q₁} y d it is defined by means of the table of figure 2.1. Can also be used the following list to define the function d

(q₀, a) = q₁(q₀, b) = q₀

(q₁, a) = q₁(q₁ ,b) = q₀

the transition diagram is in figure 2.2.

consider another example. DFA M= {Q, S , q₀, F, d } accepts the L(M)={w Î {a, b}* to, consecutive three b } * that does not contain b’s } and this represented by:

Q={q₀, q₁, q₂, q₃}

S ={a, b}

q₀=q₀

F={q₀, q₁, q₂}

And s given by the table of figure 2.3.

FINITE ROBOTS NONC Determinísticos (NFA’S).

Nondeterminístico a finite robot is a villa tupla ( Q, S , q₀, d , F) in where Q, S , q₀ and F (states, entrances, initial state and final states) have the same meaning that stops a DFA, but in this case? it is a transformation of Q x S a 2^Q. (Recuérdese that 2Q is the set of powers of Q, the set of all the subgroups of Q). Obsérvese that since ^d it is a relation for all pair(q, s ) ade up of the present state and the symbol of the entranced (q, s ),

is a zero more state or collection of [ that is to say, d (q, s )Í Q ]. This indicates that, for all state q1 can be had the zero or alternative ones to choose like following state, all for the same symbol of entrance.

The term nondeterminístico finite robot is brief generally like NFA of its abbreviations in English Nondeterministic Finite Automaton. If M is a NFA, we will define the language acepatdo by M by means of L(M)={ w ½ w is a chain accepted by M } where a chain w is accepted by M, if M passes of their initial state to their state of acceptance or end when crossing w (w is consumed in its totality).

The described NFA accepts the language formed by any number (including the zero) of a’, concatenated to a "b" or one "to" concatenated to nobody I number (including the zero) of b’s One imagines of the following form:

Q={q₀, q₁, q₂, q₃, q₄}

F={q₂, q₃, q₄}

q₀₌q₀

S ={a, b}

The fact that cells exist with Æ it indicates that any transition does not exist from the present state by means of the corresponding entrance. That for a pair (been present, entrance) it exists more of a possible following state indicates that it is possible to be chosen between the different possibilities. In the model nothing exists that determines the election. Therefore, one says that the behavior of the robot is nondeterminist. Let us see another example. Let us consider the NFA M={ Q, S , q₀, F, d } that accepts the language formed by chains that have zero or more occurrences of "ab" or "aba" and this dice by:

Q={q₀, q₁, q₂} S ={a, b}

q₀₌q₀F={q₀}