[TPI] Wyrażenia regularne.

[Sebastiano]

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

[machina13]

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 --

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ś

[Sebastiano]

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 --

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}\) ?

[machina13]

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?

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

[Sebastiano]

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 --

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]

\(\displaystyle{ 10 ^{*} 10 ^{*} = 10 ^{*}}\)

[Sebastiano]

\(\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?

[machina13]

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ęć.

[Sebastiano]

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!