Regular and context-free pattern languages over small alphabets
conference contributionposted on 25.07.2012, 13:44 by Daniel ReidenbachDaniel Reidenbach, Markus L. Schmid
Pattern languages are generalisations of the copy language, which is a standard textbook example of a context-sensitive and noncontext- 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.
- Computer Science