Чередование (формальная теория языка)
В формальной теории языка и сопоставлении с образцом чередование — это объединение двух наборов строк или, что эквивалентно, логическая дизъюнкция двух шаблонов, описывающих наборы строк.
Регулярные языки закрыты относительно чередования, что означает, что чередование двух регулярных языков снова является регулярным. [1] В реализациях регулярных выражений чередование часто выражается вертикальной чертой, соединяющей выражения для двух языков, объединение которых должно быть сопоставлено, [2] [3] в то время как в более теоретических исследованиях для этой цели может использоваться знак плюс . [1] Возможность построения конечных автоматов для объединений двух регулярных языков, которые сами определяются конечными автоматами, является центральной для эквивалентности между регулярными языками, определяемыми автоматами и регулярными выражениями. [4]
Другие классы языков, которые закрыты относительно чередования, включают контекстно-свободные языки и рекурсивные языки . Вертикальная черта для обозначения чередования используется в языке SNOBOL и некоторых других языках. В формальной теории языка чередование является коммутативным и ассоциативным . Это в общем случае не относится к форме чередования, используемой в языках сопоставления с образцом, из-за побочных эффектов выполнения сопоставления в этих языках.
Ссылки
- ^ ab Linz, Peter (2006). "Теорема 4.1". Введение в формальные языки и автоматы . Jones & Bartlett Learning. стр. 100–101. ISBN 9780763737986.
- ^ Фицджеральд, Майкл (2012). «Alternation». Знакомство с регулярными выражениями: распутывание регулярных выражений, шаг за шагом . O'Reilly Media. стр. 43–45. ISBN 9781449338893.
- ^ "Чередование с вертикальной чертой". regular-expressions.info . Получено 11.11.2021 .
- ^ Купер, Кит; Торцон, Линда (2011). Разработка компилятора (2-е изд.). Elsevier. стр. 41. ISBN 9780080916613.
Библиография
- Джон Э. Хопкрофт и Джеффри Д. Ульман, Введение в теорию автоматов, языков и вычислений , Addison-Wesley Publishing, Рединг, Массачусетс, 1979. ISBN 0-201-02988-X .
.svg/1280px-Encoder_Disc_(3-Bit).svg.png) | Эта статья по комбинаторике — заглушка . Вы можете помочь Википедии, расширив ее. |
.svg){kind=link}
