Problem Detail: I’m looking for mathematical theories that deal with describing formal languages (set of strings) in general and not just grammar hierarchies.
Asked By : mtanti
Answered By : Raphael
There are plenty of possibilities. Others have already mentioned automata which offer a rich selection. Consider the following frameworks, too:
- Some languages can be defined directly by (co)inductive definitions. For instance, the smallest fixpoint of
$qquad begin{align*} phantom{a} &phantom{Rightarrow} varepsilon in L w in L &Rightarrow aw in L aw in L &Rightarrow baw in L phantom{a} end{align*}$
is the same language as the one described by $(bamid a)^*$, the largest fixpoint is $(bamid a)^omega$. Note that such a definition can also be written in calculus or inference rule form:
$ qquad begin{align*} phantom{a} frac{}{varepsilon}, quad frac{w}{aw}, quad frac{aw}{baw} phantom{a} end{align*}$ - Words define word structures that can be used as models of logical formula. Essentially, every word defines the domain of its positions $D_w = {1, dots, n}$, predicates $P_a : D to {0,1}$ so that $P_a(i) Longleftrightarrow w_i = a$ for all $a in Sigma$, a predicate $<$ that is $<$ from $mathbb{N}$ restricted to $D_w$ and a predicate $operatorname{suc} : D_w times D_w to {0,1}$ that is true if and only if the second parameter is the direct successor of the fist.
So for instance, if $w = aababaab$ then
$ qquad begin{align*} phantom{a} S_w models forall, i. forall, j. (P_b(i) land operatorname{suc}(i,j)) to lnot P_b(j); phantom{a} end{align*}$
in fact, this first-order formula defines—via the set of all word structures that fulfill it—the same language as $(bamid a)^*$. The corresponding $omega$-language $(bamid a)^omega$ is described by the LTL formula
$ qquad begin{align*} phantom{a} square,(P_b tobigcirc(lnot P_b)) phantom{a} end{align*}$
Several equivalences between classic language classes and certain logics are known. For example, FO corresponds to star-free languages, weak MSO to regular languages and MSO to $omega$-regular languages. See here for references. - Something orthogonal to classic classes are pattern languages. Assume a terminal alphabet $Sigma$ and a variable alphabet $X={x_1, x_2,dots}$. A string $p in (Sigma cup X)^+$ is called a pattern. Let $mathcal{H}= {sigma mid sigma : X to Sigma^*}$ the set of substitutions. We define the language of a pattern $p$ as
$ qquad begin{align*} phantom{a} mathcal{L}(p) = {sigma(p) mid sigma in mathcal{H}}. phantom{a} end{align*}$
Note that $sigma$ is extended to work on patterns; terminal symbols are left unchanged.
As an example, consider $mathcal{L}(x_1abbax_1)= {wabbawmid w in {a,b}^*}$.
Note that we allow substitutions to delete variables; some properties of the class of pattern languages are hugely different for deleting vs. non-deleting substitutions. Pattern languages are of particular interest in Gold-style learning.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/813
