Cheap and Secure Web Hosting Provider : See Now

[Answers] What is examples of languages to prove the inclusions between families of languages generated by matrix grammars?

, , No Comments
Problem Detail: 

$\lambda M_{ac}$ = family of languages generated by matrix grammar with appearance checking and with erasing rules

$\lambda M$ = family of languages generated by matrix grammar without appearance checking and with erasing rules

$M_{ac}$ = family of languages generated by matrix grammar with appearance checking and without erasing rules

$M$ = family of languages generated by matrix grammar without appearance checking and without erasing rules

$RE$ = family of recursive enumerable languages

It is stated in [1] that

(a) $\lambda M \subset \lambda M_{ac} = RE$,

(b) $M \subset M_{ac} \subset CS$,

(c) $M \subseteq \lambda M$.

$M_{ac}$ can generate the language $L = \{a^{2^m} : m \geq 0 \}$, but $M$ probably cannot (if I'm not mistaken). Thus this yield the (b) above.

What are the examples of languages that can be used to prove the (a) and (c)?

Your shared wisdom, advice or hints are very appreciated.

[1] http://aleteya.cs.buap.mx/~jlavalle/papers/rewriting/tarraphd.pdf

Asked By : kate

Answered By : Hendrik Jan

The paper you link (Grammars with Regulated Rewriting, Jürgen Dassow, manuscript, 2006) gives more hints. Look at Theorem 2. The four types of matrix grammars are equivalent to the (slightly more general) four classes of regularly controlled grammars.

The fact that grammars without appearance checking are strictly less powerful than those with ac seems to have been obtained by Hauschildt and Jantzen. It is a consequence that without ac the languages over a single letter alphabet are regular. Dassow: "Since the known proofs for statement [..] use deep results from the theory of Petri nets [..] we omit a proof".

This should prove strict inclusions in (a) and (b). The inclusion in (c) is perhaps not known to be strict? It is just inclusion in Theorem 1 (iii).

D. Hauschildt, M. Jantzen, Petri net algorithms in the theory of matrix grammars. Acta Informatica 31 (1994) 719–728. doi 10.1007/BF01178731

Abstract. This paper shows that the languages over a one-letter alphabet generated by context-free matrix grammars are always regular. Moreover we give a decision procedure for the question of whether a context-free matrix language is finite. Hereby we strengthen a result of [Mäkinen, E.: On the generative capacity of context-free matrix grammars over one-letter alphabet 92] and settle a number of open questions in [Dassow, J., Pâun, G.: Regular rewriting in formal language theory 89]. Both results are obtained by a reduction to Petri net problems.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53340

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback