[Solved]: Are there other ways to describe formal languages other than grammars?

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:

1. 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 $(ba\mid a)^*$, the largest fixpoint is $(ba\mid 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*}$

2. 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 $(ba\mid a)^*$. The corresponding $\omega$-language $(ba\mid a)^\omega$ is described by the LTL formula
   $ \qquad \begin{align*} \phantom{a}\\ \square\,(P_b \to\bigcirc(\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.

3. 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)= \{wabbaw\mid 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