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

Да се построи КДА за езика


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


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

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

МнениеПуснато на: Sun Mar 29, 2009 7:15 pm    Заглавие: Да се построи КДА за езика

зад.4. Да се построи КДА за езика [tex]L[/tex]
г)
[tex]L=\left\{ \alpha \in \left\{0,1\right\}* | \alpha \cyr{с точно едно срещане на 010 като поддума} \right\}[/tex]


Така за решението имам няколко трудности ако докажа, че даден регулярен израз отговаря на езика,то по Теоремата на Стефан Клини следва ли,че може да се построи КДА ,който да разпознава езика ,отговарящ на регулярния израз?

Така 1-воначално започвам с доказателството по намирането на регулярния израз:

Нека[tex] \beta=010[/tex], тогава [tex]\alpha=\gamma . \beta . \xi[/tex],където [tex]\gamma=\left\{1\right\}*.\left\{0\right\}*[/tex] и [tex]\xi=\left\{0\right\}*.\left\{1\right\}*[/tex][tex]<=> \alpha=\left\{\gamma|\gamma=\left\{1\right\}*.\left\{0\right\}*\right\}[/tex].[tex]\left\{\beta=(010) \right\}[/tex][tex]\left\{\xi|\xi=\left\{0\right\}*.\left\{1\right\}*\right\}=>\alpha=\left\{0 \right\}*.\left\{1 \right\}*.010.\left\{0 \right\}*.\left\{1 \right\}*[/tex] и от Т.На Стефан Клини следва,че може да се построи КДА по този регулярен израз, който да разпознава езикът [tex]L[/tex] .

/*Но това дали е варно 1-во и 2-ро дали така може да се докаже */

Така получавам автомата отбелязан с 1 на картинката и правя опит да го детерминирам по правилата и се получава 2 ,който на пръв поглед генерира други думи например няма само 010 , има винаги 10101 като подпоследователност .И за това искам да питам имам ли право да детерминирам автоамта 1? Той няма състояния, от които да излизат две ребра с един и същ етикет ,но има [tex]\epsilon[/tex] . Моля помогнете..



Graph.JPG
 Description:
 Големина на файла:  10.31 KB
 Видяна:  3757 пъти(s)

Graph.JPG


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







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

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


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

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

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

[tex]\alpha=\left\{0 \right\}*.\left\{1 \right\}*.010.\left\{0 \right\}*.\left\{1 \right\}*[/tex]
не е регулярен израз, съответстващ на поставената задача. Според условито думата [tex]1010[/tex] трябва да се разпознава от автомата, но не се поражда от регулярния ти израз. Не е ли по-добре просто да си направиш автомата, без да използваш регулярен израз. Иначе задачата не е толкова трудна.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Hannibal
Начинаещ


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

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

МнениеПуснато на: Mon Mar 30, 2009 7:00 pm    Заглавие:

е нали звездата на Клини означава 0-ла ,1 .... ∞ пъти от 1-та звезда 0-ла пъти нулата от втората звезда 1-цата веднъж 010 и после нищо не разпознава ли 1010 , моля разясни Rolling Eyes ,щом ти го казваш значи наистина ми е грешно, но аз прилагам това ,което сме учили. Ако се пробвам да напиша автомата и после да го докажа ,че той разпознава езика според мен ще стане по-трудно ,защото може и да не се сетя за автомата, като в действителност не се сещам. Моля разясни ми къде е грешката в логиката чрез регулярните изрази,ще ти бъда много признателен.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
nikko1
Напреднал


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

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

МнениеПуснато на: Wed Apr 01, 2009 10:47 am    Заглавие:

Ами [tex]\{0\}^*.\{1\}^*[/tex] означава конкатенация (слепване) на дума съдържаща от 0 то безброй нули и дума съдържаща от 0 то безброй единици. Вероятно искаш да напишеш нещо от вида [tex](0+1)^*[/tex] но тогава няма как да следиш дали не е минала поддума от вида 010. Иначе съм объркал за 1010 (тя се разпознава), но ето ти вече верен пример за дума, която не се разпознава от регулярния ти израз [tex]11011010[/tex].
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Hannibal
Начинаещ


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

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

МнениеПуснато на: Wed Apr 01, 2009 7:31 pm    Заглавие:

Аха тук си напълно прав,но [tex](0+1)^{*}[/tex] какво означава [tex](0\cup 1)^{*}[/tex] ?
И тогава как ще се реши задачата? Rolling Eyes
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Hannibal
Начинаещ


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

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

МнениеПуснато на: Sat Apr 04, 2009 11:10 pm    Заглавие:

Така 1-во една забележка в 01010 се среща 2-ти 010,защото не е казано в условието ,че трябва да са дизюнктни поддумите.
Разглеждам 1-во езика състоящ се от думи с поне две срещания на 010 като поддума.
Регулярният израз за този език е:[tex]\Sigma^*\left( 010\Sigma^*\cap \Sigma.\Sigma^*.010\Sigma^*\right)[/tex]
И за нашата задачи казваме така, трябват ни тезу думи [tex]\alpha[/tex] съдържащи точно веднъж 010 и не съдържащи поне два пъти 010 =>
[tex]\alpha=\Sigma^*010\Sigma^{*}\cap\overline{\Sigma^*\left( 010\Sigma^*\cap \Sigma.\Sigma^*.010\Sigma^*\right)} [/tex]
След това правим по регулярните изрази автомат и го детерминираме и минимизираме.
ПП Искам да питам отрицанието как се прави.Правим [tex]\Sigma^*\left( 010\Sigma^*\cap \Sigma.\Sigma^*.010\Sigma^*\right)[/tex] и после крайните стават начални ,а началните стават крайни ,така ли?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
complex
Напреднал


Регистриран на: 08 Nov 2007
Мнения: 296

Репутация: 31.9Репутация: 31.9Репутация: 31.9
гласове: 6

МнениеПуснато на: Sat Jun 13, 2009 4:36 pm    Заглавие:

Прекалено сложно ми се вижда, няма ли по-лесен начин..??
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Hannibal
Начинаещ


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

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

МнениеПуснато на: Sat Jun 13, 2009 6:19 pm    Заглавие:

Доста тежка ,задача ,но такава на контролното няма да се падне бъди сигурен.
ПО ленесн начин може и да има ,но с повече разсъждения, които може да го направят дори по-сложен.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
complex
Напреднал


Регистриран на: 08 Nov 2007
Мнения: 296

Репутация: 31.9Репутация: 31.9Репутация: 31.9
гласове: 6

МнениеПуснато на: Sun Jun 14, 2009 4:28 pm    Заглавие:

А няма ли да стане така: 1*(00)*(11)*.010.(11)*(00)*1* ?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
BeckhamStZ
Начинаещ


Регистриран на: 03 Apr 2008
Мнения: 86

Репутация: 11.4
гласове: 3

МнениеПуснато на: Sun Jun 14, 2009 8:17 pm    Заглавие:

Описания начин от Hannibal е верен
да имаме точно 1 срещане означава да нямаме две или повече срещания пресечено с поне 1 срещане.
Допълнението се прави като направиш допълнение на финалните състояния
т.е. финално става НЕфинално, а НЕфинално става финално.
началното се запазва!

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

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