Регистрирайте сеРегистрирайте се

Да се построи КДА за думи делящи се на 8


 
   Форум за математика Форуми -> Дискретната математика
Предишната тема :: Следващата тема  
Автор Съобщение
Hannibal
Начинаещ


Регистриран на: 13 Apr 2008
Мнения: 91

Репутация: 11.8
гласове: 2

МнениеПуснато на: Wed Mar 25, 2009 10:14 pm    Заглавие: Да се построи КДА за думи делящи се на 8

зад.1.
Нека [tex]\Sigma=\{0,1,2,3,4,5,6,7,8,9\}[/tex].Да се построи краен детерминиран автомат за:
а)езика [tex]L_1=[/tex]{[tex]\alpha \in \Sigma* | \alpha[/tex] се дели на 8,разглеждано като число}

Така моля помогнете и то основно с логиката.Ще искажа моите разсъждения,но те ме доведоха до огромен граф, който не мога да детерминирам.
За да се дели на 8 ,числото образувано от последните 3-ри цифри трябва да се дели на 8 ,н.п. 123456008,9256,314159264.
Нека [tex]A_i=[/tex]{[tex]\alpha \in [/tex]{[tex]\Sigma[/tex]}* дава остатък [tex]i[/tex] при деление на 8}
Нека [tex]\alpha \in A_0 ; [/tex]
[tex]\alpha=a_1a_2a_3....a_n [/tex]
[tex]\alpha_0 =\underbrace{a_1a_2a_3..a_n}_{\cyr{ostat\cdprimek 0-la pri delenie na 8}}=0[/tex]
[tex]\alpha_1\in A_1[/tex] [tex]\alpha_1=10*\underbrace{a_1a_2a_3..a_n}_{\cyr{ostat\cdprimek 0-la pri delenie na 8}} +1=1[/tex]
[tex]\alpha_2\in A_2[/tex]
....
[tex]\alpha_8\in A_0[/tex]
[tex]\alpha_9\in A_1[/tex]
и така провеждаме разсъждения когато [tex]\alpha \in A_1[/tex] и прибавяме всяка една от цифрите после когато [tex]\alpha \in A_2[/tex] ..... и т.н.
така обхващам всички случаи.Но графът се получава огромен и немога да го детерминирам посмъртно.Моля помагайте и казвайте къде бъркам.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
nikko1
Напреднал


Регистриран на: 23 Nov 2008
Мнения: 422

Репутация: 61.8
гласове: 36

МнениеПуснато на: Wed Mar 25, 2009 11:55 pm    Заглавие:

Не е нужно да разглеждаш признак за делене на 8. Просто си правиш състояния за всички остатъжи по модул 8. Иначе правилно си се ориентирал.
Ето ти пример за състоянията [tex]s[/tex] - начално, незаключително, за да не се разпознава празната дума [tex]\epsilon[/tex]. След това следват 8 състояния [tex]q_i,\,0\leq i\leq 7[/tex] като в състояние [tex]q_i[/tex] автоматът се намира тогава и само тогава, когато получената до момента дума е десетичен запис на число, което дава остатък [tex]i[/tex] при делене с 8. Така само състоянието [tex]q_0[/tex] ще е заключително. Остава да си зададеш функцията на прехода [tex]\delta[/tex].
Ако например се намираш в състояние [tex]q_i[/tex] и постъпи символ [tex]j[/tex] за [tex]0\leq j\leq 9[/tex], то имаше [tex]\delta(q_i,\,j)=q_{(10.i+j)\,\tex{mod}\ 8}.[/tex]
Ще ти дам и пример за първите 2-3 състояния на автомата и за два прехода. За съжаление ще имаш 9 състояния и 90 прехода, така че имаш доста да пишеш. А можеш да не рисуваш целия автомат. Просто написваш всички състояния и правиш таблица на преходите - в редовете пишеш състоянията, в стълбовете цифрите от 0 до 9, а в самата таблица - прехода от даденото състояние с дадената цифра.

P.S. За съжаление явно е пълна квотата за снимки във форума, така че се налага да хостна снимката на въшнен сайт.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Hannibal
Начинаещ


Регистриран на: 13 Apr 2008
Мнения: 91

Репутация: 11.8
гласове: 2

МнениеПуснато на: Thu Mar 26, 2009 6:54 pm    Заглавие:

[tex]\begin{array}{|c|c|c|c|c|c|c|c|c|} &q_0 & q_1 & q_2 & q_3 & q_4 & q_5 & q_6 & q_7 &S\\\hline 0 & q_0 & q_2 & q_4 & q_6 & q_5 & q_2 & q_4 & q_6 &P\\ 1 & q_1 & q_3 & q_5 & q_7 & q_6 & q_3 & q_5 & q_7& q_1\\ 2 & q_2 & q_4 & q_6 & q_0 & q_7 & q_4 & q_6 & q_0&q_2\\3 & q_3 & q_5 & q_7 & q_1 & q_0 & q_5 & q_7 & q_1&q_3\\4 & q_4 & q_6 & q_0 & q_2 & q_1 & q_6 & q_0 & q_2&q_4\\5 & q_5 & q_7 & q_1 & q_3 & q_2 & q_7 & q_1 & q_3&q_5\\6 & q_6 & q_0 & q_2 & q_4 & q_3 & q_0 & q_2 & q_4&q_6\\7 & q_7 & q_1 & q_3 & q_5 & q_4 & q_1 & q_3 & q_5&q_7\\8 & q_0 & q_2 & q_4 & q_6 & q_5 & q_2 & q_4 & q_6&q_0\\9 & q_1 & q_3 & q_5 & q_7 & q_6 & q_3 & q_5 & q_7&q_1\\\end{array}[/tex]
Според мен трябва от първоначалното състояние [tex]S[/tex] с 0-ла да отиваме в друго състояние [tex]P[/tex] ,което да е второ крайно и от което да не излиза нищо,така взимаме числото 0-ла, което се дели на 8 без остатък и не генерираме думи от рода на 00008 например.
Автомата ако не се лъжа е детерминиран, но в задачата се иска да се минимизира.
За това правим нашия автомат тотален ,т.е. добавяме буквите от [tex]\Sigma[/tex] да излизат от [tex]P[/tex] и да отиват в няков [tex]q_{\cyr{prazno}}[/tex] ,което не е крайно и започваме минимизацията ,разделяме след кратки преобразования състоянията на 7 групички [tex]*A_0[/tex]={[tex]P[/tex]},[tex]*A_1=[/tex]{[tex]q_0[/tex]},[tex]A_2=[/tex]{[tex]q_4[/tex]},[tex]A_3=[/tex]{[tex]q_1,q_5[/tex]},[tex]A_4=[/tex]{[tex]q_2,q_6[/tex]},[tex]A_5=[/tex]{[tex]q_3,q_7[/tex]},->[tex]A_6=[/tex]{[tex]S[/tex]}
И правим тези нови 7 групи като състояния и следим от таблицата къде отиват и правим минимизирания автомат,нали така?

Добре направили сме автомата, но как ще докажем ,че той е търсеният ,може би с индуция по дължината на думата ? Но има ли някаква теорема ,от която директно да следва без да доказваме,че построеният автомат е търсеният и ако има как се казва и какво гласи?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Дискретната математика Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2021 math10.com.