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

КНА към КДА и др.


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


Регистриран на: 02 Mar 2009
Мнения: 3


МнениеПуснато на: Mon Mar 02, 2009 3:43 pm    Заглавие: КНА към КДА и др.

Здравейте, може ли някой да ми обясни принципа на решение и как се решават следните примерни задачи:

Благодаря.



зад.2.JPG
 Description:
зад.2
 Големина на файла:  30.5 KB
 Видяна:  6265 пъти(s)

зад.2.JPG



zad1.JPG
 Description:
зад.1
 Големина на файла:  45.66 KB
 Видяна:  6265 пъти(s)

zad1.JPG


Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







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

Върнете се в началото
TheBlueOne
Начинаещ


Регистриран на: 02 Mar 2009
Мнения: 3


МнениеПуснато на: Mon Mar 02, 2009 8:04 pm    Заглавие:

Edit: Зад.1 я разбрах как се решава.

Изключително ще съм благодарен ако някой каже нещо за другата, с регулярният израз. Rolling Eyes
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
nikko1
Напреднал


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

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

МнениеПуснато на: Tue Mar 03, 2009 12:02 am    Заглавие:

Ами прави се така.
1) От регулярния израз правиш недетерминиран краен автомат.
2) От НДКА правиш детерминиран краен автомат, евкивалентен на НДКА-то.
3) След като имаш ДКА го правиш пълен и минимизираш.

Ето ти НДКА за твоята задача, да се надяваме, че нататък ще се справиш сам. Виждам че знаеш как се детерминира автомат.



xy.png
 Description:
 Големина на файла:  11.07 KB
 Видяна:  6219 пъти(s)

xy.png



nda.png
 Description:
 Големина на файла:  30.3 KB
 Видяна:  6219 пъти(s)

nda.png


Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
TheBlueOne
Начинаещ


Регистриран на: 02 Mar 2009
Мнения: 3


МнениеПуснато на: Tue Mar 03, 2009 1:32 pm    Заглавие:

nikko1 написа:
Ами прави се така.
1) От регулярния израз правиш недетерминиран краен автомат.
2) От НДКА правиш детерминиран краен автомат, евкивалентен на НДКА-то.
3) След като имаш ДКА го правиш пълен и минимизираш.

Ето ти НДКА за твоята задача, да се надяваме, че нататък ще се справиш сам. Виждам че знаеш как се детерминира автомат.


Благодаря за отговора.
Да, 2-ра и 3-та точки е ясно как стават, само че не разбрах как точно от този регулярен израз стигна до този автомат въпреки разяснението от първата фиг. Можеш ли да ми обясниш като за "for dummies" Embarassed стъпка по стъпка как става?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Hannibal
Начинаещ


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

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

МнениеПуснато на: Tue Mar 24, 2009 8:29 pm    Заглавие:

Така надявам се ,че "+" означава обединение ако съдя по каквото се получава за [tex](X U Y)*[/tex]
1. Имаш [tex]X U Y[/tex] Това означава или едното или другото,чертаеш си първо какво означава [tex]X[/tex],а после [tex]Y[/tex] ,после ги свързваш с [tex]\epsilon[/tex] (епсилон) преход ,тоест ги свързваш с "нищото" помежду си и получаваш картинка 2.
Детерминираш го и получаваш картинка 3, после имаш [tex](X U Y)*[/tex] тази звезда означава ,че се повтаря [tex]0,1....,n[/tex] пъти за това добавяш ново състияние,което е крайно ,за да обхванеш празната дума и го свързваш с епсилон към графа от картинка 3,като добавяш още 2-ва епсилон прехода, за да може да се повтарят буквите. и Като последно го минимизираш и получаваш онзи дето питаш от къде се взе.

ПП Моля да бъде хвърлено едно око на поста ми от по-знаещите да не съм объркал нещо. Wink



X U Y.JPG
 Description:
 Големина на файла:  27.47 KB
 Видяна:  6105 пъти(s)

X U Y.JPG


Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Erzimion
Начинаещ


Регистриран на: 07 Apr 2009
Мнения: 7


МнениеПуснато на: Tue Apr 07, 2009 10:17 am    Заглавие: Здрасти

Може ли някои да ми помогне с литература или сайтове (по възможност на бг) отностно детерминираните крайни автомати, недерминирани крайни автомати и обеснение с конюкция, дезюнкция и как по точно се стига до полинома на Жигалкин, ровя, ровя и намирам някой неща но все още не ми е напално ясно. Ще съм благодарен ... нужни са ми материалите защото ме чака изпит по Дискр. мат.

Като информация мога да кажа какво ми се падна предният път :
Да се построй ДКА които започва с 0,1 и има четен брой 0 и нечетен брой 1, автомата да завършва на 0,1.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
nikko1
Напреднал


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

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

МнениеПуснато на: Tue Apr 07, 2009 3:14 pm    Заглавие:

Имаш предвид [tex]L=\{\gamma\in\{0,\,1\}^*|\gamma=01\alpha01,\,N_0(\gamma)=2k,\,N_1(\gamma)=2l-1,\, k,\,l\in\mathbb{N}\},[/tex] където [tex]N_i(\gamma)[/tex] е броят на симвлите i в [tex]\gamma[/tex]?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Erzimion
Начинаещ


Регистриран на: 07 Apr 2009
Мнения: 7


МнениеПуснато на: Wed Apr 08, 2009 1:12 pm    Заглавие:

Формулата е до някаде ми е ясна, но идва проблема със самият автомат, просто не ми е много ясно как да въртя подадените нули и единици, така че крайния резултат да е винаги четни нули/единици и нечетни нули/единиц (съжалявам просто забравих за кое от двете числа казох, че е четно и нечетно). Единственото решение до което успях да стигна е нечетните, независимо какво се поадава и да завърши на {0,1}. А ако имаш нещо подходящо из нет-а по Дискретна мат. бих се радвал да узная, дали БГ или Анг. не ми е чак такъв проблем. Wink Като знан, че времето ми намаля ... и на китайски да е пак ще ми свърши работа стига да науча поне нещо ! Laughing
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
nikko1
Напреднал


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

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

МнениеПуснато на: Wed Apr 08, 2009 2:17 pm    Заглавие:

Просто те питах за условието, за да мога да ти помогна. Доста съмнително ми е такова условие, защото това да започва с 0, 1 не знам какво значи. Да започва с един символ, който е нула или едно или да започва задължително с префикса 01? Освен това що азбуката ти е нули и единици и думата ти е с 2 или повече символа, то със сигурност ще започва с 0 или 1 и ще завършва на нула или едно. За да може да се помогне на някого с някоя задача трябва да е ясно условието, а при теб не е. Дори не си казал дали азбуката ти каква е [tex]V=\{0,\,1\}[/tex] или има и други символи.
За литература ето ти тук има достъпна от сайта на авторите. Това са учебник и сборник с решени задачи, като и двата са на български език.
учебник
сборник
Ако това не ти е достатъчно можеш да видиш в някоя библиотека учебника на Красимир Манев, Увод в дискретната математика.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Erzimion
Начинаещ


Регистриран на: 07 Apr 2009
Мнения: 7


МнениеПуснато на: Wed Apr 08, 2009 3:00 pm    Заглавие:

Извинявам се за което ... и си прав разбира се, но нямам условията пред мен, а и съм на работа. По късно като се прибера ще драсна някой друг ред със задачата както е дефинирана. Благодаря ти много за информацията с учебника и зборника, ще ги разгледам моментално ! Wink
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Erzimion
Начинаещ


Регистриран на: 07 Apr 2009
Мнения: 7


МнениеПуснато на: Thu Apr 09, 2009 1:18 pm    Заглавие:

Та извинявам се за закаснението, но работа какво да се прави... Ето я задачата:

Да се построй ДКА, който разпознава всички думи от {0,1}*, който имат нечетен брой 0-ли и четен брой 1-ници и завършват с 01. Да се построй и автоматна граматика, пораждаща този език.

А другата задача е следната:

Дадена е двоичната функция f1=(x(стрелка на Пирс)(y+z))\equiv ((x(импликация) y,z))+(x|z))

a)да се построи формула за тази функция над множеството {(стрелка на Шефер,Стрелка на Пирс, отрицание)} // синволите незнам как да ти ги изкарам за това ги пиша с думи

б) Да се построи полином на Жигалкин за тази функция;

в) да се определи принадлежността на функцията f1 на затворените класове T>sub>0, T1,L;
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
v1rusman
Напреднал


Регистриран на: 18 Jul 2007
Мнения: 318

Репутация: 39.5Репутация: 39.5Репутация: 39.5Репутация: 39.5
гласове: 10

МнениеПуснато на: Thu Apr 09, 2009 1:52 pm    Заглавие:

Извинявам се предварително ако въпросът ми е глупав, но какво учите в университета ? Това материал от някакъв допълнителен курс ли е или ?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
nikko1
Напреднал


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

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

МнениеПуснато на: Thu Apr 09, 2009 2:18 pm    Заглавие:

Искаш ли помощ със задачите или предпочиташ да се праобваш сам, след като вече имаш учебник и сборник?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Erzimion
Начинаещ


Регистриран на: 07 Apr 2009
Мнения: 7


МнениеПуснато на: Thu Apr 09, 2009 2:32 pm    Заглавие:

Така нека почна от там, 1-ви курс задочно обучение сам в Шуменския университет "Еп. К. Преславски". Това са задачи който ми се паднаха на изпит-а, две от тях. За преподавателите ... единия е готин, нещата могат се схванат при него, асистента. Разбрах наскоро от приятели, че предподавателят ми е бил наскоро учител в някакво даскало и са го назначили в у-нито. За да се посмеем малко, раказаха ми, че дори и 3-ка да изкараш на устния изпит при варпсоната доц. ти пише 2-ка защото можеш повече Laughing Така е професионално изкривяване, което на мен не би ми допаднало, по простата причина, че това ми е 2-рото висше и в момента работя и уча и времето ми е наистина малко, а особено че не сам се занимавал с каквато и да е математика 4-тири години това е др. тема на разговор и в момента се старая да се справя и да науча нещо, за жалост колкото и да го чета, абсолютно нищо не разбирам, е някой работи само, не са ми достатачни.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Erzimion
Начинаещ


Регистриран на: 07 Apr 2009
Мнения: 7


МнениеПуснато на: Thu Apr 09, 2009 2:34 pm    Заглавие:

Със задачите ... трудно ще се справя защото нямам време, сабота ми е самият изпит, ако може да ми помогнеш ... не би отказал. Това което ми даде като линкове е чудесно, найстина е по разбираемо от това което изнамерих из нета. Благодаря ти ! Wink
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
nikko1
Напреднал


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

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

МнениеПуснато на: Thu Apr 09, 2009 3:24 pm    Заглавие:

1 зад. Налага се да напишеш първо недетерминиран краен автомат, който разпознава езика, след това да го детерминираш. След това автоматната граматика е лесна. Ето ти идея какво да направиш, за да намериш НДКА-то.
Определяш си вътрешните състояния, като спазваш логиката на условието. Ясно е, че ще трябва по някакъв начин да следим четността/нечетността на нулите и единиците на думата. Първо записваме езика така
[tex]L=\{\gamma\in\{0,\,1\}^*| \gamma=\alpha01, N_0(\alpha)=2k, N_1(\alpha)=2l-1,\ k,\,l\in\mathbb{N}\}.[/tex]
Задаваме вътрешните състояния на автомата:
[tex]q_0[/tex] - начално, като в това състояние ще се намира автомата, ако досега имаме четен брой нули и четен брой единици.
[tex]q_1[/tex] - в това състояние ще се намира автомата, ако досега имаме четен брой нули и нечетен брой единици.
[tex]q_2[/tex] - това състояние ще се намира автомата, ако досега имаме нечетен брой нули и четен брой единици.
[tex]q_3[/tex] - в това състояние ще се намира автомата, ако досега имаме нечетен брой нули и нечетен брой единици.
И ще добавим още две състояния, с който да следим думата да завършва на 01.
[tex]q_4[/tex] - минали са четен брой нули и нечетен брой единици, след което е дошла 0.
[tex]q_5[/tex] - минали са четен брой нули и нечетен брой единици, след което са дошли 01. Това състояние ще е единственото заключително.
Автомата е недетерминиран, защото няма как да определим, че остават 2 символа до края на думата. За да не чертая диаграма на автомата ще ти дам таблица на функцията на преходите [tex]\delta[/tex] и ще обясня (частично) защо е такава.
[tex]\delta(q_0,\,0)=q_2[/tex] (защото от четен брой нули и четен единици е дошла нула, значи стават нечетен нули и четен единици, т.е. състояние [tex]q_2[/tex]), [tex]\delta(q_0,\,1)=q_1[/tex] (защото от четен брой нули и четен единици е дошла единица, значи стават четен нули и нечетен единици, т.е. [tex]q_1[/tex]).
[tex]\delta(q_1,\,0)={q_3,\,q_4}[/tex] (тук имаме 2 прехода, защото в думата отзад може да има още само 01 и трябва да се разпознава, затова отиваме в q_3, а ако е по-дълга просто продължаваме да следим четността), [tex]\delta(q_1,\,1)=q_0[/tex].
[tex]\delta(q_2,\,0)=q_0[/tex], [tex]\delta(q_2,\,1)=q_3[/tex]
[tex]\delta(q_3,\,0)=q_1[/tex], [tex]\delta(q_3,\,1)=q_2[/tex]
[tex]\delta(q_4,\,0)=\emptyset[/tex], [tex]\delta(q_4,\,1)=q_5[/tex]
[tex]\delta(q_5,\,0)=\emptyset[/tex], [tex]\delta(q_5,\,1)=\emptyset[/tex].
За теб остава да си детерминираш автомата и да напишеш от ДКА автоматната граматика. За втора се опитай сам, ако не можеш ще ти помогна с б) и в).
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Erzimion
Начинаещ


Регистриран на: 07 Apr 2009
Мнения: 7


МнениеПуснато на: Thu Apr 09, 2009 3:45 pm    Заглавие:

Благодаря ти ! Ами ще се опитам сам, стига сичко на готово нали така? Wink ДОстатачно ми помогна и благодаря за което !!! Я кажи само от каде ги чаткаш толкова тея работи с дискретната математика ? Smile
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Methuselah
VIP


Регистриран на: 17 Feb 2007
Мнения: 1057
Местожителство: София
Репутация: 105.9
гласове: 20

МнениеПуснато на: Thu Apr 09, 2009 11:17 pm    Заглавие:

v1rusman написа:
Извинявам се предварително ако въпросът ми е глупав, но какво учите в университета ? Това материал от някакъв допълнителен курс ли е или ?

Т'ва не е ли от стандартния курс по дискретна математика?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
bora
Начинаещ


Регистриран на: 06 Sep 2009
Мнения: 1


МнениеПуснато на: Sun Sep 06, 2009 2:43 pm    Заглавие:

Здравейте,
имам един въпрос за РИ и краен автомат -
имаме даден РИ , трябва да се построи КА, който разпознава езика, представен от РИ (ab*+ac)b + (a+b)(cca*b)*
Знам,че този израз се разделя на две части и се строи автомат за двете отделни части,после се обединяват. Някой може ли да ми помогне да разбера как точно става това.
Благодаря ви много!
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Дискретната математика Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

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