Markov algorithm

The Russian mathematician Andrei Markov developed by the Markov algorithm is an important approach to the formalization of the concept of algorithm dar. particular tasks of symbolic data processing, for example, conjugation and declension of natural languages ​​, can be solved with its help very efficient.

  • 2.1 incrementation and addition
  • 2.2 Recognition of correct bracket expressions

Definition

Informal Description

Of Markov algorithm considers the input data of an algorithm as words or phrases of which by a translation result can be determined. The principle of the solution is therefore based solely on the substitution of strings. Other operations are not available. Analogous to Turing machine is a symbol string used as a basic data structure. Although production systems usually make a non-deterministic processing of such strings of symbols, can be achieved by special restrictions, a deterministic behavior:

  • Multiple rules can be applied, the application order must always be clearly defined
  • If a rule application at several positions of the output word possible, a priority must be defined always

The Markov algorithm meets the requirements for such a deterministic word calculus. By means of computability theory one can prove that Markov algorithms are just as powerful as any other algorithms, Turing machines or μ - recursive functions.

Formal definition

Markov algorithm and natural algorithm represent semi-Thue systems whose rules form an ordered set, which in turn breaks down into the following disjoint subsets:

  • Terminating rules
  • Non-terminating rules

Under the following conditions the word Q from the P word by a rule R is derivable directly in a Markov algorithm:

  • P generated by a non-terminating control
  • R is the first applicable rule in P
  • Q is generated by applying R to the most left -to-find substring of R in P

The operation of the Markov algorithm terminates with the word that has been generated by a rule or terminating at no other rule is applicable. In contrast to the post- calculus is always operates only on the appropriate parts of the word. The substitution of a word pair (P, Q ) is the basis of the Markov algorithm:

  • A given output word is searched for the first containment of the word P
  • Can P are found, it is replaced by the word Q

There are the following special cases of the substitution:

  • ε ⇒ Q The empty word is replaced by a word Q.
  • P ⇒ ε A word P is replaced by the empty word.
  • ε ⇒ ε The empty word is replaced by itself.

The words to be processed are made from an alphabet A. Left and right parts of the rules of a Markov algorithm provide words of the alphabet a; following metacharacters may not be included in the alphabet:

  • ⇒ being used as a substitution operator
  • . identifies terminating rules

Operation

Flow chart

On the input word to be processed takes place a search on the left word the first rule. Is this included in the input word, the rule is triggered corresponding substitution. The input word is scanned from left to right. Thus, substituting for a multiple occurrence of the left word typically is always the left-most occurrence.

If the search is unsuccessful described above, moving on to the next rule. Can the involvement of all other rules no substitution will be made ​​, then the algorithm is finished. The application of a terminating rule leads to its termination. Has been substituted by a non- terminating control, the entire process begins again, taking into account the amended word.

Simple Case Study

For the explanations to the flowchart even a simple case study to explain the operation; especially the order of the control application, and the results thereof are well illustrated in the following.

The input word used in the example is:

I_I_I_I_ In addition, the following rules are defined:

01 I -> A   02 _- > B   03 AB > _B   04 BBBBBBBB- > I_I_I_I_ This produces the following substitutions, the number of applied rule was preceded by:

1 A_I_I_I_     1 A_A_I_I_     1 A_A_A_I_     1 A_A_A_A_     2 ABA_A_A_     2 ABABA_A_     2 ABABABA_     2 ABABABAB     3 _BABABAB     2 BBABABAB     3 BB_BABAB     2 BBBBABAB     3 BBBB_BAB     2 BBBBBBAB     3 BBBBBB_B     2 BBBBBBBB     4 I_I_I_I_ application Examples

Incrementing and adding

The representation of numbers in the decimal system is not optimal for the solution of the problem. However, one uses a simple Unärcode, there is the algorithm for incrementing or addition each of only a single rule.

View as:

  • Coding the numbers is carried out in the form of I = 1, 2 = II, III, etc. 3 =
  • The addition of 1 0 2 4 IIII II is encoded for example as I

This results in the following solution:

  • ε ⇒. I incrementing
  • ⇒ ε addition

Recognition correct bracket expressions

The key to solving this problem lies in finding and painting of brackets couples. Coated brackets disappear and their place is occupied by the adjacent character or characters. Now the brackets of the following pairs are directly adjacent and in turn, can easily be found. For our example, it is assumed that the term in brackets is bounded on both sides by the character ' $'.

This results in the following solution:

  • () ⇒ ε Deleting a pair of parentheses
  • $ $ ⇒ $ .1 $ All pairs deleted, result is 1
  • ( ⇒ 0 ) ⇒ 0 Delete the rest brackets
  • 00 ⇒ 0 Delete all excess zeros

The shown form for solving the problem is very simple and understandable. The Markov algorithm provides here the problem well adapted solution principle.

 

Change of variables Church–Turing thesis Semi-Thue-System Automata theory
551324
de