文章基本信息

标题：言語の測度に基づく非正規性の証明技法
本地全文：下载
作者：新屋良磨
期刊名称：コンピュータソフトウェア
印刷版ISSN：0289-6540
出版年度：2017
卷号：34
期号：1
页码：1_119-1_124
DOI：10.11309/jssst.34.1_119
出版社：Japan Society for Software Science and Technology
摘要：与えられた言語が非正規であることの証明技法として，ポンピング補題や右同値類の有限性 (Myhill-Nerodeの定理) などの手法が有用であることが広く知られている．本論文ではこれらの手法とは全く異なる新しい非正規性の証明技法を提案する．いくつかの例題を通じて提案手法の新規性・有用性を議論し，さらに提案手法の課題についても具体的に述べる．提案技法は言語の測度に基づくものであり，「与えられた言語 L がほとんど空(測度が 0 )である」という直観的な性質を非正規性の証明に用いる．