К разложению регулярных языков в задаче поиска в полуструктурированных базах данных. Н.Ф. Алексиадис(ЦНТК РАН) Е. Е. Хазова (мех-мат МГУ им. М. В. Ломоносова) - презентация

1 К разложению регулярных языков в задаче поиска в полуструктурированных базах данных. Н.Ф. Алексиадис(ЦНТК РАН) Е. Е. Хазова (мех-мат МГУ им. М. В. Ломоносова)

2 DB1 DB2

3

4 Пример : L = c (c+d)(ab+c) (a+d) = e1e2e3e4 e1 = c e2 = c+d e3 = ab+c e4 = a+d L = ccaba + cdabd + ccca + ccc(a+d) +cc(ab+ab+ab)(a+d) ….. Подход 1: Решить «языковое» уравнение вида L = EX, где L, E – данные регулярные языки. Пример :

5 Class C: R = e2e3e1 R = e3e1e3e2 Class CI: R = e2e1(e1*e3*)* R = e2e3(e2*e3*)* R = e1(e1*(e3e3*e1)*)*e2(e1*e3*)* R в классе CI есть перезапись языка L, если (R) L (R) = L - функция перезаписи R = e2e3e1~ a (aa)* (aaa)*=L Подход 2:

6 Class CI: (R1) = L (e0e1e1) = L (R2) L Пример:

7

8

9 Свойство конечной степени Частный случай R = e1(e1e2)*e1*e2*