Loading article…
形式言語理論とパターン マッチングでは、交替とは2 つの文字列セットの結合、またはそれと同等に、文字列セットを記述する 2 つのパターンの 論理和です。
正規言語は交替に関して閉じており、2つの正規言語の交替もまた正規であることを意味する。 [1]正規表現の実装では、交替は、和集合が一致する2つの言語の式を縦棒で結んで表現されることが多いが、[2] [3]より理論的な研究では、この目的のためにプラス記号が代わりに使用されることもある。[1]有限オートマトンによって定義された2つの正規言語の和集合に対して有限オートマトンを構築できることは、オートマトンによって定義された正規言語と正規表現によって定義された正規言語の同等性にとって中心的なものである。[4]
交替に関して閉じている他の言語のクラスには、文脈自由言語と再帰言語があります。交替を表す縦棒表記は、SNOBOL言語やその他の言語で使用されています。形式言語理論では、交替は可換かつ結合的です。これは、パターン マッチング言語で使用される交替の形式には一般に当てはまりません。これは、これらの言語で一致を実行すると副作用が生じるためです。
参考文献
- ^ ab リンツ、ピーター (2006)。「定理 4.1」。形式言語とオートマトン入門。ジョーンズ＆バートレット学習。pp. 100–101。ISBN 9780763737986。
- ^ フィッツジェラルド、マイケル (2012)。「交替」。正規表現入門: 正規表現をステップバイステップで解明する。オライリーメディア。pp. 43–45。ISBN 9781449338893。
- ^ 「垂直バーによる交替」。regular-expressions.info 。 2021年11月11日閲覧。
- ^ クーパー、キース、トルゾン、リンダ (2011)。コンパイラのエンジニアリング (第 2 版)。エルゼビア。p. 41。ISBN 9780080916613。
文献
- John E. Hopcroft と Jeffrey D. Ullman、『オートマトン理論、言語、計算入門』、Addison-Wesley Publishing、マサチューセッツ州リーディング、1979 年。ISBN 0-201-02988 -X。