Всего на сайте:
148 тыс. 196 статей

Главная | Математика

Итерация Р*.  Просмотрен 69

ОПЕРАЦИИ НАД ЯЗЫКАМИ

1) конкатенация языковP Q = {pq | pÎP, q Î Q}, т.е. это множество слов, получаемых всевозможными приписываниями к словам из языка Р слов из языка Q;

2) объединениеP ∪ Q;

итерация Р*.

Заметим, что операция конкатенации не коммутативна, в отличие, от объединения, т.е. P Q≠Q P.

Множество всех языков над Х, вместе с перечисленными операциями образуют алгебру, которая называется алгеброй Клини:

< > – алгебра Клини.

Определение.Определим рекурсивно формулу, т.е. регулярное выражение f над алфавитом Х, и регулярный язык L(f), задаваемый этим выражением:

1) e, x, Æ -- регулярные выражения (формулы). Они задают языки:   
  L(е) = е; L(Æ) = Æ; L(х) = х;   
2) если P и Q — регулярные выражения, то L(P Q) = L(P) L(Q);  
  а) P Q — регулярное выражение;  
  б) P ∪ Q — регулярное выражение; L(P ∪ Q) = L(P) L(Q);
  в) P* — регулярное выражение; L(P*) = P*;
3) других нет.   

 

В соответствии с определением языка, будем отождествлять формулу и язык, который она задаёт. Будем также считать, что операция операция «*» имеет самый высокий приоритет, а операция «∪» — самый низкий, тогда в регулярных выражениях можно опускать лишние скобки.

 

Примеры регулярных выражений: PQ, (PQ)*, (P*Q)*.

Предыдущая статья:Moglie, aglio, famiglia, Campidoglio, figlia, maglione, tovaglia, coniglio, Следующая статья:Некоторые эквивалентные преобразования формул
page speed (0.1302 sec, direct)