й сомножитель соответствует пропозициональной переменной
При этом 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
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий