Изменения

Пример: <tex>(ab(cd))(ef).</tex> Группа <tex>№1 </tex> {{---}} <tex>(ab(cd)),\,</tex> группа <tex>№2 </tex> {{---}} <tex>(cd),\,</tex> группа <tex>№3 </tex> {{---}} <tex>(ef)</tex>

#: <tex>L=((0\,|\,1)^∗)\backslash 1.</tex>

Если какому-то нетерминалу <tex>A</tex> соответствуют несколько регулярных выражений <tex>r_1, r_2, \dotsc, r_n</tex>, заменить их на одно: <tex>A=((r_1)\,|\,(r_2)\,|\,\dotsc\,|\,(r_n))\,</tex> (очевидно, что оно также будет соответствовать этому нетерминалу).

Регулярное Допустим, группа <tex>№1</tex> соответствует нетерминалу <tex>S,\,</tex> группы <tex>№2-№5</tex> {{---}} нетерминалам <tex>A-D</tex> соответственно. # Для каждого нетерминала составим регулярное выражение:#: <tex>S\leftrightarrow ((?2)(?3))\\S\leftrightarrow\varepsilon\\A\leftrightarrow ((?1)(?1))\\B\leftrightarrow ((?4)(?5))\\C\leftrightarrow c\\D\leftrightarrow d</tex># Объединим регулярные выражения, соответствующие одинаковым нетерминалам:#: <tex>S\leftrightarrow (((?2)(?3))\,|\,\varepsilon)\\A\leftrightarrow ((?1)(?1))\\B\leftrightarrow ((?4)(?5))\\C\leftrightarrow c\\D\leftrightarrow d</tex># Искомое регулярное выражение соответствует нетерминалу <tex>S,\,</tex> однако оно ссылается на группы, отличные от <tex>S.</tex> Будем рекурсивно заменять такие ссылки на сами регулярные выражения до тех пор, пока в исходном регулярном выражении не останутся только терминалы и ссылки на стартовый нетерминал <tex>S</tex>:#: <tex>(((?2)(?3))\,|\,\varepsilon)\rightarrow(((?1)(?1)(?3))\,|\,\varepsilon)\rightarrow(((?1)(?1)(?4)(?5))\,|\,\varepsilon)\rightarrow(((?1)(?1)c(?5))\,|\,\varepsilon)\rightarrow(((?1)(?1)cd)\,|\,\varepsilon).</tex> Таким образом, регулярное выражение для этой грамматики будет выглядеть так: <tex>(((?1)(?1cd1)cd)\,|\,\varepsilon).</tex>