言語とオートマトンの理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/13 04:21 UTC 版)
「木接合文法」の記事における「言語とオートマトンの理論」の解説
木接合文法は、文脈自由文法よりも強力だが文脈依存文法よりも弱い。 具体例として、任意の文字列を二回繰り返すような言語を記述することができる。より一般には、 { a n b n c n d n | 1 ≤ n } {\displaystyle \{a^{n}b^{n}c^{n}d^{n}|1\leq n\}} のような文脈自由文法に含まれない言語を記述することができる。このような処理はembedded pushdown automatonで表現できる。一方で、文字列を3回繰り返す言語や、5つ以上の文字をそれぞれ同じ長さで順に並べた列からなる言語は木接合文法では生成できない。 木接合文法は弱文脈依存文法の1つであり、よってチョムスキー階層には当てはまらないが、その関連性はよく研究されている。
※この「言語とオートマトンの理論」の解説は、「木接合文法」の解説の一部です。
「言語とオートマトンの理論」を含む「木接合文法」の記事については、「木接合文法」の概要を参照ください。
ウィキペディア小見出し辞書の「言語とオートマトンの理論」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 言語とオートマトンの理論のページへのリンク
