Предишната тема :: Следващата тема |
Автор |
Съобщение |
Hannibal Начинаещ
Регистриран на: 13 Apr 2008 Мнения: 91
гласове: 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] . Моля помогнете..
Description: |
|
Големина на файла: |
10.31 KB |
Видяна: |
4449 пъти(s) |
|
|
|
Върнете се в началото |
|
|
Реклама
|
Пуснато на: Заглавие: Реклама |
|
|
|
|
Върнете се в началото |
|
|
nikko1 Напреднал
Регистриран на: 23 Nov 2008 Мнения: 422
гласове: 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
гласове: 2
|
Пуснато на: Mon Mar 30, 2009 7:00 pm Заглавие: |
|
|
е нали звездата на Клини означава 0-ла ,1 .... ∞ пъти от 1-та звезда 0-ла пъти нулата от втората звезда 1-цата веднъж 010 и после нищо не разпознава ли 1010 , моля разясни ,щом ти го казваш значи наистина ми е грешно, но аз прилагам това ,което сме учили. Ако се пробвам да напиша автомата и после да го докажа ,че той разпознава езика според мен ще стане по-трудно ,защото може и да не се сетя за автомата, като в действителност не се сещам. Моля разясни ми къде е грешката в логиката чрез регулярните изрази,ще ти бъда много признателен.
|
|
Върнете се в началото |
|
|
nikko1 Напреднал
Регистриран на: 23 Nov 2008 Мнения: 422
гласове: 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
гласове: 2
|
Пуснато на: Wed Apr 01, 2009 7:31 pm Заглавие: |
|
|
Аха тук си напълно прав,но [tex](0+1)^{*}[/tex] какво означава [tex](0\cup 1)^{*}[/tex] ?
И тогава как ще се реши задачата?
|
|
Върнете се в началото |
|
|
Hannibal Начинаещ
Регистриран на: 13 Apr 2008 Мнения: 91
гласове: 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
гласове: 6
|
Пуснато на: Sat Jun 13, 2009 4:36 pm Заглавие: |
|
|
Прекалено сложно ми се вижда, няма ли по-лесен начин..??
|
|
Върнете се в началото |
|
|
Hannibal Начинаещ
Регистриран на: 13 Apr 2008 Мнения: 91
гласове: 2
|
Пуснато на: Sat Jun 13, 2009 6:19 pm Заглавие: |
|
|
Доста тежка ,задача ,но такава на контролното няма да се падне бъди сигурен.
ПО ленесн начин може и да има ,но с повече разсъждения, които може да го направят дори по-сложен.
|
|
Върнете се в началото |
|
|
complex Напреднал
Регистриран на: 08 Nov 2007 Мнения: 296
гласове: 6
|
Пуснато на: Sun Jun 14, 2009 4:28 pm Заглавие: |
|
|
А няма ли да стане така: 1*(00)*(11)*.010.(11)*(00)*1* ?
|
|
Върнете се в началото |
|
|
BeckhamStZ Начинаещ
Регистриран на: 03 Apr 2008 Мнения: 86
гласове: 3
|
Пуснато на: Sun Jun 14, 2009 8:17 pm Заглавие: |
|
|
Описания начин от Hannibal е верен
да имаме точно 1 срещане означава да нямаме две или повече срещания пресечено с поне 1 срещане.
Допълнението се прави като направиш допълнение на финалните състояния
т.е. финално става НЕфинално, а НЕфинално става финално.
началното се запазва!
П.С. За допълнението се изисква детерминиран автомат!
а сечението може да се представи по закона на Де Морган
|
|
Върнете се в началото |
|
|
|