Случайный афоризм
Очень трудно писать то, что является исключительно вашим изобретением, оставаясь при этом верным другому тексту, который вы анализируете. Жак Деррида
 
новости
поиск по автору
поиск по тематике
поиск по ключевому слову
проба пера
энциклопедия авторов
словарь терминов
программы
начинающим авторам
ваша помощь
о проекте
Книжный магазин
Главная витрина
Книги компьютерные
Книги по психологии
Книги серии "Для чайников"
Книги по лингвистике
ЧАВо
Разные Статьи
Статьи по литературе

Форма пользователя
Логин:
Пароль:
регистрация
 детектив



 драмма



 животные



 история



 компьютерная документация



 медицина



 научно-популярная



 очередная история



 очерк



 повесть



 политика



 поэзия и лирика



 приключения



 психология



 религия



 студенту



 технические руководства



 фантастика



 философия и мистика



 художественная литература



 энциклопедии, словари



 эротика, любовные романы



в избранноеконтакты

Параметры текста
Шрифт:
Размер шрифта: Высота строки:
Цвет шрифта:
Цвет фона:

шины  P, n(P), n(n(P)) и т.д., пока не обнаружится такая, из ко-
торой выходит стрелка с буквой y.  Та  вершина,  в  которую  эта
стрелка ведет, и будет нашим следующим положением.

     Остается  понять,  как  для каждой вершины дерева вычислить
указатель на значение функции n в этой вершине. Это делается как
раньше, при этом значения n для более коротких слов используются
при вычислении очередного значения функции n. Это означает,  что
вершины  дерева  следует  просматривать в порядке возрастания их
длины. Нетрудно понять, что все это можно  уложить  в  требуемое
число действий (хотя константа зависит от числа букв  в  алфави-
те).  Относящиеся  к этому подробности см. в главе об алгоритмах
на графах.

     Можно поинтересоваться, какие свойства слов можно распозна-
вать с помощью конечных автоматов. Оказывается,  что  существует
просто описываемый класс образцов, задающий все такие свойства -
класс регулярных выражений.

     Определение.  Пусть  фикисирован конечный алфавит Г, не со-
держащий  символов  'l', 'e', '(', ')', '*' и '|' (они будут ис-
пользоваться для построения регулярных выражений и не должны пе-
ремешиваться с буквами). Регулярные выражения строятся по  таким
правилам:

     (а) буква алфавита Г - регулярное выражение;
     (б) символы 'l', 'e' - регулярные выражения;
     (в)  если A,B,C,..,E - регулярные выражения, то (ABC...E) -
          регулярное выражение.
     (г)   если   A,B,C,..,E   -   регулярные   выражения,    то
          (A|B|C|...|E) - регулярное выражение.
     (д) если A - регулярное выражение, то A* - регулярное выра-
          жение.

Каждое  регулярное  выражение задает множество слов в алфавите Г
по таким правилам:

     (а) букве соответствует одноэлементное множество, состоящее
         из однобуквенного слова, состоящего из этой буквы;
     (б)  символу  'e' соответствует пустое множество, а символу
         'l' - одноэлементное множество, единственным  элементом
         которого является пустое слово;
     (в) регулярному выражению (ABC...E) соответствует множество
         всех слов, которые можно получить, если к  слову  из  A
         приписать слово из B, затем из C,..., затем из E ("кон-
         катенация" множеств);
     (г)   регулярному   выражению  (A|B|C|...|E)  соответствует
         объединение   множеств,   соответствующих    выражениям
         A,B,C,..,E;
     (д) регулярному выражению A* соответствует "итерация"  мно-
         жества, соответствующего выражению A, то есть множество
         всех  слов,  которые  можно так разрезать на куски, что
         каждый кусок  принадлежит  множеству,  соответствующему
         выражению  A.  (В частности, пустое слово всегда содер-
         жится в A*.)

     Примеры

Выражение               Множество


1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 18 : 19 : 20 : 21 : 22 : 23 : 24 : 25 : 26 : 27 : 28 : 29 : 30 : 31 : 32 : 33 : 34 : 35 : 36 : 37 : 38 : 39 : 40 : 41 : 42 : 43 : 44 : 45 : 46 : 47 : 48 : 49 : 50 : 51 : 52 : 53 : 54 : 55 : 56 : 57 : 58 : 59 : 60 : 61 : 62 : 63 : 64 : 65 : 66 : 67 : 68 : 69 : 70 : 71 : 72 : 73 : 74 : 75 : 76 : 77 : 78 : 79 : 80 : 81 : 82 : 83 : 84 : 85 : 86 : 87 : 88 : 89 : 90 : 91 : 92 : 93 : 94 : 95 : 96 : 97 : 98 : 99 : 100 : 101 : 102 : 103 : 104 : 105 : 106 : 107 : 108 : 109 : 110 : 111 : 112 : 113 : 114 : 115 : 116 : 117 : 118 : 119 : 120 : 121 : 122 : 123 : 124 : 125 : 126 : 127 : 128 : 129 : 130 : 131 : 132 : 133 : 134 : 135 : 136 : 137 : 138 : 139 : 140 : 141 : 142 : 143 : 144 : 145 : 146 : 147 : 148 : 149 : 150 : 151 : 152 : 153 : 154 : 155 : 156 : 157 : 158 : 159 : 160 : 161 : 162 : 163 : 164 : 165 : 166 : 167 : 168 : 169 : 170 : 171 : 172 : 173 : 174 : 175 : 176 : 177 : 178 : 179 : 180 : 181 : 182 : 183 : 184 : 185 : 186 : 187 : 188 : 189 : 190 : 191 : 192 : 193 : 194 : 195 : 196 : 197 : 198 : 199 : 200 : 201 : 202 : 203 : 204 : 205 : 206 : 207 : 208 : 209 : 210 : 211 : 212 : 213 : 214 : 215 : 216 : 217 : 218 : 219 : 220 : 221 : 222 : 223 : 224 : 225 : 226 : 227 : 228 : 229 : 230 : 231 : 232 : 233 : 234 : 235 : 236 : 237 : 238 : 239 : 240 : 241 : 242 : 243 : 244 : 245 : 246 : 247 : 248 : 249 : 250 : 251 : 252 : 253 : 254 : 255 : 256 : 257 : 258 : 259 : 260 : 261 : 262 : 263 : 264 : 265 : 266 : 267 : 268 : 269 : 270 : 271 : 272 : 273 : 274 : 275 : 276 : 277 : 278 : 279 : 280 : 281 : 282 : 283 : 284 : 285 : 286 : 287 : 288 : 289 : 290 : 291 : 292 : 293 : 294 : 295 : 296 : 297 : 298 : 299 : 300 : 301 : 302 : 303 : 304 : 305 : 306 : 307 : 308 : 309 : 310 : 311 : 312 : 313 : 314 : 315 : 316 : 317 : 318 : 319 : 320 : 321 : 322 : 323 : 324 : 325 : 326 : 327 : 328 : 329 : 330 : 331 : 332 : 333 : 334 : 335 : 336 : 337 : 338 : 339 : 340 : 341 : 342 : 343 : 344 : 345 : 346 : 347 : 348 : 349 : 350 : 351 : 352 : 353 : 354 : 355 : 356 : 357 : 358 : 359 : 360 : 361 : 362 : 363 : 364 : 365 : 366 : 367 : 368 : 369 : 370 : 371 : 372 : 373 : 374 : 375 : 376 : 377 : 378 : 379 : 380 : 381 : 382 : 383 : 384 : 385 : 386 : 387 : 388 : 389 : 390 : 391 : 392 : 393 : 394 : 395 : 396 : 397 : 398 : 399 : 400 : 401 : 402 : 403 : 404 : 405 : 406 : 407 : 408 : 409 : 410 : 411 : 412 : 413 : 414 : 415 : 416 : 417 : 418 : 419 : 420 : 421 : 422 : 423 : 424 : 425 :
главная наверх

(c) 2008 Большая Одесская Библиотека.