Чередование (формальная теория языка)
В теории формального языка и сопоставлении с образцом — чередование это объединение двух наборов строк или, что то же самое, логическое дизъюнкция двух шаблонов, описывающих наборы строк.
Регулярные языки закрыты при чередовании, а это означает , что чередование двух регулярных языков снова регулярно. [1] В реализациях регулярных выражений чередование часто выражается вертикальной чертой, соединяющей выражения для двух языков, объединение которых должно сопоставляться. [2] [3] в то время как в более теоретических исследованиях знак плюса . для этой цели может использоваться [1] Способность создавать конечные автоматы для объединений двух регулярных языков, которые сами определяются конечными автоматами, имеет центральное значение для эквивалентности между регулярными языками, определяемыми автоматами и регулярными выражениями. [4]
К другим классам языков, закрытым при чередовании, относятся контекстно-свободные языки и рекурсивные языки .Обозначение чередования вертикальной чертой используется в языке SNOBOL и некоторых других языках.В теории формального языка чередование является коммутативным и ассоциативным . В целом это не относится к форме чередования, используемой в языках сопоставления с образцом, из-за побочных эффектов выполнения сопоставления в этих языках.
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б Линц, Питер (2006). «Теорема 4.1» . Введение в формальные языки и автоматы . Джонс и Бартлетт Обучение. стр. 100–101. ISBN 9780763737986 .
- ^ Фицджеральд, Майкл (2012). «Чередование» . Знакомство с регулярными выражениями: разгадка регулярных выражений, шаг за шагом . О'Рейли Медиа. стр. 43–45. ISBN 9781449338893 .
- ^ «Чередование с вертикальной чертой» . регулярные выражения.info . Проверено 11 ноября 2021 г.
- ^ Купер, Кейт; Торчон, Линда (2011). Разработка компилятора (2-е изд.). Эльзевир. п. 41. ИСБН 9780080916613 .
Библиография
[ редактировать ]- Джон Э. Хопкрофт и Джеффри Д. Ульман, Введение в теорию автоматов, языки и вычисления , издательство Addison-Wesley Publishing, Ридинг, Массачусетс, 1979. ISBN 0-201-02988-X .
 | Эта комбинаторике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |