Математическая теория формальных языков


         

й сомножитель соответствует пропозициональной переменной


При этом i- й сомножитель соответствует пропозициональной переменной xi

и выбирается следующим образом:



  • если данная элементарная дизъюнкция не содержит ни литерала xi, ни литерала , то используем выражение (a+b);


  • если она содержит литерал xi, но не содержит литерала , то используем выражение a;


  • если она содержит литерал , но не содержит литерала xi, то используем выражение b;


  • если она содержит оба литерала xi и , то используем выражение 0.


Если m > 1, то построим по указанному методу для каждой из булевых формул C1, C2, ..., Cm

регулярное выражение и возьмем их сумму.

Легко видеть, что два построенных так регулярных выражения равны тогда и только тогда, когда булева формула

невыполнима.

Пример 15.9.2.

Пусть . Регулярные выражения

(a+b)(a+b)(a+b)

и

ab(a+b)+(a+b)ab+b(a+b)(a+b)+(a+b)(a+b)a

равны, так как булева формула

невыполнима (или, другими словами, булева формула

является тавтологией).

Упражнение 15.9.3.

Равны ли регулярные выражения

(a+b)(a+b)(a+b)

и

bb(a+b)+ba(a+b)+a(a+b)b+(a+b)aa ?

Упражнение 15.9.4.

Равны ли регулярные выражения

(a+b)(a+b)(a+b)(a+b)

и

aab(a+b)+a(a+b)(a+b)b+(a+b)aa(a+b)+(a+b)bb(a+b)+ +(a+b)baa+bab(a+b)+b(a+b)(a+b)b ?

Упражнение 15.9.5.

Эквивалентен ли конечный автомат

конечному автомату, изображенному ниже?


Содержание  Назад  





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий