22
$\begingroup$

I'm looking for mathematical theories that deal with describing formal languages (set of strings) in general and not just grammar hierarchies.

$\endgroup$
  • $\begingroup$ Note that there are many, many grammer types beyond the classic Chomsky ones, for instance multiple, coupled and length dependent context-free grammars, respectively (easily googlable). $\endgroup$ – Raphael Mar 27 '12 at 13:59
  • $\begingroup$ Found some related Wikipedia table with more structure and links $\endgroup$ – Anton Oct 26 '17 at 5:33
14
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

You should have a look at automata theory. There's plenty of material about it.

In example, you may define a regular language with a nondeterministic finite automaton with labelled edges: a string belongs to the language if the automaton can follow the transitions labelled by its characters and stops in a final state.

Also, a context-free grammar may be recognized by a pushdown automaton.

Another way to define languages is by means of Turing machines.

$\endgroup$
5
$\begingroup$

From the Chomsky hierarchy there are four types of formal languages(each of them is a subset of the ones after it):

A regular formal language can be described by:

  1. Regular Grammar
  2. Finite Automaton (Deterministic/Nondeterministic)
  3. Regular Expression

1., 2. and 3. are equivalent and from one of them you can construct the others.

A context-free formal language can be described by:

  1. Context-free Grammar
  2. Pushdown automaton

Also 1. and 2. are equivalent.

A context-sensitive formal language can be described by:

  1. Linear bounded automaton (Turing machine with restricted tape)

A recursively enumerable formal language can be described by:

  1. Total Turing machine
$\endgroup$
  • $\begingroup$ And all the other language classes? $\endgroup$ – Raphael Mar 27 '12 at 13:13
  • $\begingroup$ And the classless languages? $\endgroup$ – Dave Clarke Mar 27 '12 at 14:08
  • $\begingroup$ Chomsky doesn't say these are the only types of languages - they are just four types he finds important, and we still find them important, but there are many other types. $\endgroup$ – reinierpost Sep 24 '14 at 13:09
5
$\begingroup$

Further to the other answers, one can describe and classify languages in terms of "generators" and closure properties. For example, it makes sense to talk about the smallest AFL generated by some language. A good place to start learning about this type of description is this book, although it can be quite hard to find a hard copy of it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.