Matematyka.pl

Witam!
Mam dwa takie zadania:
1. Napisz wyrażenie regularne obrazujące słowo \(\displaystyle{ 00100100110100101001}\)
2. Wyrażenie regularne \(\displaystyle{ (a+k+m)* t(i+o+w)* (c+i+k)*e}\) generuje zbiór do którego należy:
a)matowe b)katowic c)kotwice d)matwik

Bardzo byłbym wdzięczny o wytłumaczenie krok po kroku,lub link do jakiegoś fajnego materiału na temat prostych wyrażeń regularnych. Te przykłądy rozwiązuje sie według jakiegoś określonego szablonu? Bo większość materiałów w internecie jest napisana bardzo formalnie i ciężko to zrozumieć.
Z góry dziękuje. Pozdrawiam

1. gdy masz słowo podane w systemie binarnym zawsze możesz dać jako wyrażenie je opisujące \(\displaystyle{ \left( 0+1\right) ^{*}}\) . Jeśli jednak byś chciał napisać coś innego można to zrobić tak:
na początku twojej liczby mamy powtarzający się ciąg \(\displaystyle{ 001}\) to będzie początek naszego wyrażenia: \(\displaystyle{ \left( 001\right) ^{*}}\)
dalej mamy powtarzający się ciąg \(\displaystyle{ 1010}\) więc dopisujemy do wyrażenia \(\displaystyle{ \left( 10\right) ^{*}}\) no i patrzymy dalej. zostaje nam \(\displaystyle{ 0101001}\) no to dalej idąc powyższą metodą powtarza nam się \(\displaystyle{ 01}\) dopisujemy więc \(\displaystyle{ \left( 01\right) ^{*}}\) zostaje nam \(\displaystyle{ 001}\) które się już nie powtarza wiec na koniec \(\displaystyle{ 001}\). Teraz sklejamy wyrażenie regularne do kupy i mamy \(\displaystyle{ \left( 001\right) ^{*} \left( 10\right) ^{*}\left( 01\right) ^{*}001}\)

Oczywiście jest to jedno z możliwych rozwiązań, których jest nieskończenie wiele i wydaje mi się że sposób też jest prosty.-- 22 lut 2012, o 13:16 --

Sebastiano pisze:Witam!

2. Wyrażenie regularne \(\displaystyle{ (a+k+m)* t(i+o+w)* (c+i+k)*e}\) generuje zbiór do którego należy:
a)matowe b)katowic c)kotwice d)matwik

na końcu wyrażenia mamy e bez gwiazdki, czyli występuje ono tam zawsze 1 raz. Dlatego odrzucamy juz na starcie odpowiedzi b i d.
Rozpatrzyć musimy wobec tego odpowiedzi a i c.
Zacznijmy od rozpisania tego wyrażenia na pewne zbiory
niech
\(\displaystyle{ Q=\left\{ a, k, m, EPS \right\}}\)
\(\displaystyle{ W=\left\{ t \right\}}\)
\(\displaystyle{ E=\left\{ i, o, w, EPS \right\}}\)
\(\displaystyle{ R=\left\{ c, i, k, EPS \right\}}\)
\(\displaystyle{ T=\left\{e \right\}}\)

gdzie EPS = epsilon ale z uwagi na występowanie małego e wolę oznaczyć to tak aby się nie pomylilo
teraz biorąc kolejne elementy słowa musimy sprawdzać czy możemy ułożyć to słowo biorąc literki ze zbiorów na zasadzie od lewej do prawej.(jak nie ma potrzebnej literki w aktualnym zbiorze to idziemy do zbioru następnego, nie możemy wracać).

więc przykład a)

\(\displaystyle{ matowe}\)
\(\displaystyle{ m \in Q}\)
\(\displaystyle{ a \in Q}\)
\(\displaystyle{ t \not\in Q}\) napotkaliśmy literę której w zbiorze Q nie ma, idziemy do kolejnego zbioru

\(\displaystyle{ towe}\)
\(\displaystyle{ t \in W}\)
\(\displaystyle{ o \not\in W}\)
nie ma litery o w zbiorze W, przechodzimy do kolejnego
\(\displaystyle{ owe}\)
\(\displaystyle{ o \in E}\)
\(\displaystyle{ w \in E}\)
\(\displaystyle{ e \not\in E}\)
kolejny zbiór
\(\displaystyle{ e \not\in R}\)
i ostatni
\(\displaystyle{ e \in T}\)

udało się opisać całe słowo więc jest ono opisane przez to wyrażenie
Teraz podpunkt c)

\(\displaystyle{ kotwice}\)
\(\displaystyle{ k \in Q}\)
\(\displaystyle{ o \not\in Q}\)
idziemy do kolejnego zbioru
\(\displaystyle{ o \not\in W}\)

tutaj dochodzimy do sytuacji gdy potrzebujemy litery której zbiór nie zawiera ale nie możemy przejść do kolejnego zbioru "na pusto" z tego ponieważ ten zbiór nie zawiera \(\displaystyle{ EPS}\)

dlatego odpowiedź c nie jest opisana przez to wyrażenie, mam nadzieję że zrozumiałeś

Teraz rozumiem ten sposób. Czyli w zad. 1. wynika że możemy zapisać jako: \(\displaystyle{ (0+01)^{*} 10^{*} 10^{*} (0+01)^{*}}\), czy istnieje jeszcze możliwość skrócenia tego?

-- 22 lut 2012, o 14:22 --

machina13 pisze: tutaj dochodzimy do sytuacji gdy potrzebujemy litery której zbiór nie zawiera ale nie możemy przejść do kolejnego zbioru "na pusto" z tego ponieważ ten zbiór nie zawiera \(\displaystyle{ EPS}\)

Noo, teraz wszystko jest jasne! Czyli nie możemy przeskakiwac do kolejnego zbioru jak poprzedni jest pusty i nie ma w nim żadnego elementu. I dzielenie kolejnych wyrazów na zbiory to tez super sposób. A teraz, jak na odwrót do wyrażenia regularego zapisać np słowo \(\displaystyle{ kotwica}\) ?

Sebastiano pisze:Teraz rozumiem ten sposób. Czyli w zad. 1. wynika że możemy zapisać jako: \(\displaystyle{ (0+01)^{*} 10^{*} 10^{*} (0+01)^{*}}\), czy istnieje jeszcze możliwość skrócenia tego?

na pewno chciałeś napisać 2 razy domknięcie Kleene'ego 2 razy dla 10?

machina13 pisze: tutaj dochodzimy do sytuacji gdy potrzebujemy litery której zbiór nie zawiera ale nie możemy przejść do kolejnego zbioru "na pusto" z tego ponieważ ten zbiór nie zawiera \(\displaystyle{ EPS}\)

Noo, teraz wszystko jest jasne! Czyli nie możemy przeskakiwac do kolejnego zbioru jak poprzedni jest pusty i nie ma w nim żadnego elementu. I dzielenie kolejnych wyrazów na zbiory to tez super sposób. A teraz, jak na odwrót do wyrażenia regularego zapisać np słowo \(\displaystyle{ kotwica}\) ?

a chociażby tak:
\(\displaystyle{ \left( k + o\right) ^{*} tw \left( i + c + a \right) ^{*}}\)
\(\displaystyle{ \left( k + o + t + w + i + c + a\right) ^{*}}\)
\(\displaystyle{ \left( k + p + r + m + y\right) ^{*} otwica}\)



kolejna sytuacja gdzie jest nieskończenie wiele dobrych odpowiedzi

machina13 pisze:

Sebastiano pisze:Teraz rozumiem ten sposób. Czyli w zad. 1. wynika że możemy zapisać jako: \(\displaystyle{ (0+01)^{*} 10^{*} 10^{*} (0+01)^{*}}\), czy istnieje jeszcze możliwość skrócenia tego?
na pewno chciałeś napisać 2 razy domknięcie Kleene'ego 2 razy dla 10?

Czyli: \(\displaystyle{ (0+01)^{*} 10 10^{*} (0+01)^{*}}\) z jednym domknięciem?

-- 22 lut 2012, o 17:40 --

machina13 pisze: a chociażby tak:
\(\displaystyle{ \left( k + o\right) ^{*} tw \left( i + c + a \right) ^{*}}\)
\(\displaystyle{ \left( k + o + t + w + i + c + a\right) ^{*}}\)
\(\displaystyle{ \left( k + p + r + m + y\right) ^{*} otwica}\)

kolejna sytuacja gdzie jest nieskończenie wiele dobrych odpowiedzi

Aa, czyli w tej sytuacji tworzymy takie wyrażenie jakie akurat potrzebujemy bądź szukamy Wielkie dzięki!

machina13 pisze:\(\displaystyle{ 10 ^{*} 10 ^{*} = 10 ^{*}}\)

Własnie o tego typu wzory mi chodziło Orientujesz się czy są jeszcze jakieś tego typu przydatne do wyrażeń regularnych?

nie wiem czy takie są, tu po prostu trzeba na logikę popatrzeć.
no np w powyższym po co pisać 2 razy 10, a potem jeszcze 3 razy 10 jak można napisać od razu 5 razy dziesięć.

machina13 pisze:nie wiem czy takie są, tu po prostu trzeba na logikę popatrzeć.
no np w powyższym po co pisać 2 razy 10, a potem jeszcze 3 razy 10 jak można napisać od razu 5 razy dziesięć.

Racja, po to mamy te domknięcia żeby tak tego nie rozpisywać:)Dzieki!