Regular and context-free pattern languages over small alphabets

详细信息    查看全文

• 作者：Daniel Reidenbach ; Markus L. Schmid
• 关键词：Pattern languages ; Regular languages ; Context-free languages
• 刊名：Theoretical Computer Science
• 出版年：23 January, 2014
• 年：2014
• 卷：518
• 期：Complete
• 页码：80-95
• 全文大小：395 K

文摘

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.