Let M be a Markov algorithm with alphabet Σ and terminals T. Then the set
is the language accepted by M.
Example 13.8
Consider the Markov algorithm with Σ = T = {a, b} and productions
ab → λ,
ba → λ.
Every step in the derivation annihilates a substring ab or ba, so
L(M) = {w ∈{a, b}* : n a (w) = n b (w)}.
Example 13.9
Find a Markov algorithm for
L = {a n b n : n ≥ 0}.
An answer is
ab → S,
aSb → S,
S → .λ.
If in this last example we take the first two productions and reverse the left
and right sides, we get a context-free grammar that generates the language L. In
a certain sense, Markov algorithms are simply phrase-structure grammars
is the language accepted by M.
Example 13.8
Consider the Markov algorithm with Σ = T = {a, b} and productions
ab → λ,
ba → λ.
Every step in the derivation annihilates a substring ab or ba, so
L(M) = {w ∈{a, b}* : n a (w) = n b (w)}.
Example 13.9
Find a Markov algorithm for
L = {a n b n : n ≥ 0}.
An answer is
ab → S,
aSb → S,
S → .λ.
If in this last example we take the first two productions and reverse the left
and right sides, we get a context-free grammar that generates the language L. In
a certain sense, Markov algorithms are simply phrase-structure grammars