Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436669 | Theoretical Computer Science | 2014 | 16 Pages |
Abstract
Pattern languages are generalisations of the copy language, which is a standard textbook example of a context-sensitive and non-context-free language. In this work, we investigate a counter-intuitive phenomenon: with respect to alphabets of size 2 and 3, pattern languages can be regular or context-free in an unexpected way. For this regularity and context-freeness of pattern languages, we give several sufficient and necessary conditions and improve known results.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Daniel Reidenbach, Markus L. Schmid,