Детерминированные и недетерминированные конечные автоматы  : Информатика - на REFLIST.RU

Детерминированные и недетерминированные конечные автоматы : Информатика - на REFLIST.RU

Система поиска www.RefList.ru позволяет искать по собственной базе из 9 тысяч рефератов, курсовых, дипломов, а также по другим рефератным и студенческим сайтам.
Общее число документов более 50 тысяч .

рефераты, курсовые, дипломы главная
рефераты, курсовые, дипломы поиск
запомнить сайт
добавить в избранное
книжная витрина
пишите нам
  Ссылки:
Португалия из Челябинска
Список категорий документа Информатика
Детерминированные и недетерминированные конечные автоматы

Детерминированные и недетерминированные конечные автоматы

Детерминированные, комп-ры, переходов, конечные, недетерминированные, трансляторов, разбор, проектирование, проектирование трансляторов граф переходов разбор дерево, автоматы, Детерминированные и недетерминированные конечные автоматы, Программирование и комп-ры, Программирование, дерево, граф Ключевые слова
   Книги:
страницы: 1  2  3  4 
Текущая страница: 4


 оценки стоимости преобразования НКА  в  ДКА
       рассмотрим задачу распознавания образов, в которой дана це-
       почка-текст x = a1 a2 ...  an и регулярное выражение я2ая0, на-
       зываемое образом. Мы хотим найти такой наименьший индекс j,
       что для некоторого i подцепочка ai ai+1 ...  aj  цепочки  x
       принадлежит языку, представленному выражениемя2 ая0.
           Вопросы такого рода часто возникают при  редактировании
       текстов. Многие программы для редактирования текстов разре-
       шают пользователю задавать  типы  замен  в  цепочке-тексте.
       Например пользователь может сказать,  что он хочет заменить
       слово y каким-то другим словом в куске текста х.  Чтобы вы-
       полнить такую  операцию,  программа  редактирования  текста
       должна суметь найти вхождение слова у в текст х.  Некоторые
       мощные редактирующие программы позволяют пользователю в ка-
       честве множества заменяемых  цепочек  указывать  регулярное
       множество. Например  пользователь может сказать:  "Заменить
       [I*] в х пустой цепочкой",  имея в виду,  что в  х  следует
       стереть пару квадратных скобок и символы между ними.
           Поставленную выше задачу можно переформулировать, заме-
       нив данное регулярное выражение я2а я0выражение я2b я0= I*я2aя0,  где I

       - алфавит цепочки-текста.  Можно найти первое вхождение це-
       почки из L(я2aя0) в х = а1 а2 ... аn, обнаружив кратчайший пре-
       фикс цепочки х, принадлежащий языку выражения я2bя0. Эту задачу
       можно решить,  построив  НКА М для распознавания множества,
       представленного выражением я2bя0,  а затем определить множество
       состояний в  которые  может перейти НКА М при прочтении це-
       почки а1 а2 ... аn.
           Один из  способов  моделирования поведения НКА М на це-
       почке-тексте х - превратить М в детерминированный  конечный
       автомат, используя  теорему  3.  Однако такой путь окажется
       достаточно дорогостоящим,  поскольку от регулярного выраже-
       ния я2b я0можно перейти к НКА с 2ія2bя0і состояниями, а затем к ДКА
       с почти 2 в степени 2ія2bя0і состояниями.
           Таким образом  уже  само  построение  ДКА может вызвать
       непреодолимые трудности.



          АДДДДДЩ  і
              і     і                                 ^     і
              АДДДДДЩ                                 АДДДДДЩ

                             Ршс. 4. Гррф G'

           Тръ хфшэсттхээюх рхсрю,  тхюфящхх т учхы s3 т фшруррььх
       фыя М, яюьхчхэю сшьтюыюья1 хя0, тю s3 эх тхюфшт т М'.

                                     я1b
                   ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДї
                   і                                   v
                Ъ=====ї   я1 a,bя0     Ъ=====ї     я1aя0    Ъ=====ї
                і я1s1я0  ГДДДДДДДДДДДі я1s2я0  іДДДДДДДДДґ я1s4я0  і
                А=====Щ            А=====Щ          А=====Щ
                                    і   ^
                                    АДДДЩ
                                      я1a

                             Ршс. 5. НКА М'

           Прш яюстрюхэшш ДКА М'' яю рттюьрту М' юсррчухтся тюсхьь
       сюстюяэшщ. Ню тюыьъю чхтырхх шч эшх ьюцэю  фюстшчь  шч  эр-
       чрыьэюую сюстюяэшя,  тръ  чтю юстрыьэых чхтырх ьюцэю тысрю-
       сшть.
           Прштхфхээыщ ъ  фхтхрьшэшрютрээюьу тшфу рттюьрт М'' ярш-
       тхфхэ эр ршс. 6.
           Тръшь юсррчюь  сыыю яюърчрэр тючьюцэюсть ярштхфхэшя НКА
       ъ ДКА.  Прш тръющ юяхррцшш чшсыю яюыучштшшхся сюстюяэшщ ью-
       цхт сущхсттхээю  утхышчшться,  эхъютюрых  шч эшх стрэютятся

       схсяюыхчэыьш. Сущэюсть ярштхфхэшя чръыючрхтся т тюь, чтю ьы
       шщхь юсхюфэых  яутш  фыя  фюстшцхэшя  ъюэхчэюую  сюстюяэшя,
       стрхьясь ъ тюьу,  чтюсы шсчхчыр эхюфэючэрчэюсть яхрххюфр шч
       сюстюяэшя т  сюстюяэшя  т  чртшсшьюстш ют тхюфэюую сшьтюыр.
       Этр юяхррцшя яюрюцфрхт эхсущхсттхээых сюстюяэшя ш  яюэтюьу,
       тшфшью, т  ърцфюь  шч ютфхыьэых сыучрхт рхшрть чрфрчу эуцэю
       шсхюфя шх ъюэърхтэых цхыхщ.


                      я1bя0         Ъ=======їя1      b
              ЪДДДДДДДДДДДДДДДДія1{s2,s4}я0ГДДДДДДДДДДДДДї
              і                 А=======Щ             v
              і                    і               ЪДДДДДї
              і                    і я1aя0             і я1(/)я0 іДДї
           Ъ=====ї                 і               АДДДДВЩ   і
           ія1{s1}я0 і                 і                  ^ і    і
           А=====Щ                 v                  і АДДДДЩ
              і        я1aя0        Ъ=====ї      я1bя0        ія1   a,b
              АДДДДДДДДДДДДДДДДія1{s2}я0 ГДДДДДДДДДДДДДДДЩ
                                А=====Щ
                                 ^   і
                                 АДДДЩ
                                   я1b

                             Ршс. 6. ДКА G''

           Дыя яршьхррok
$u



страницы: 1  2  3  4 
Текущая страница: 4
Список предметов Предмет: Информатика
Детерминированные и недетерминированные конечные автоматы Тема: Детерминированные и недетерминированные конечные автоматы
Детерминированные, комп-ры, переходов, конечные, недетерминированные, трансляторов, разбор, проектирование, проектирование трансляторов граф переходов разбор дерево, автоматы, Детерминированные и недетерминированные конечные автоматы, Программирование и комп-ры, Программирование, дерево, граф Ключевые слова: Детерминированные, комп-ры, переходов, конечные, недетерминированные, трансляторов, разбор, проектирование, проектирование трансляторов граф переходов разбор дерево, автоматы, Детерминированные и недетерминированные конечные автоматы, Программирование и комп-ры, Программирование, дерево, граф


Copyright c 2003 REFLIST.RU
All right reserved. liveinternet.ru
 

поиск рефератов запомнить сайт добавить в избранное пишите нам