[TPI] Wyrażenia regularne.
- Sebastiano
- Użytkownik
- Posty: 29
- Rejestracja: 9 kwie 2010, o 11:20
- Płeć: Mężczyzna
- Lokalizacja: Tychy
- Podziękował: 7 razy
- Pomógł: 2 razy
[TPI] Wyrażenia regularne.
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
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
-
- Użytkownik
- Posty: 73
- Rejestracja: 12 kwie 2009, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 16 razy
- Pomógł: 6 razy
[TPI] Wyrażenia regularne.
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 --
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ś
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 --
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.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
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
- Użytkownik
- Posty: 29
- Rejestracja: 9 kwie 2010, o 11:20
- Płeć: Mężczyzna
- Lokalizacja: Tychy
- Podziękował: 7 razy
- Pomógł: 2 razy
[TPI] Wyrażenia regularne.
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 --
-- 22 lut 2012, o 14:22 --
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 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}\)
-
- Użytkownik
- Posty: 73
- Rejestracja: 12 kwie 2009, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 16 razy
- Pomógł: 6 razy
[TPI] Wyrażenia regularne.
na pewno chciałeś napisać 2 razy domknięcie Kleene'ego 2 razy dla 10?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?
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
Ostatnio zmieniony 22 lut 2012, o 18:43 przez machina13, łącznie zmieniany 1 raz.
- Sebastiano
- Użytkownik
- Posty: 29
- Rejestracja: 9 kwie 2010, o 11:20
- Płeć: Mężczyzna
- Lokalizacja: Tychy
- Podziękował: 7 razy
- Pomógł: 2 razy
[TPI] Wyrażenia regularne.
Czyli: \(\displaystyle{ (0+01)^{*} 10 10^{*} (0+01)^{*}}\) z jednym domknięciem?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?
-- 22 lut 2012, o 17:40 --
Aa, czyli w tej sytuacji tworzymy takie wyrażenie jakie akurat potrzebujemy bądź szukamy Wielkie dzięki!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
- Sebastiano
- Użytkownik
- Posty: 29
- Rejestracja: 9 kwie 2010, o 11:20
- Płeć: Mężczyzna
- Lokalizacja: Tychy
- Podziękował: 7 razy
- Pomógł: 2 razy
[TPI] Wyrażenia regularne.
Własnie o tego typu wzory mi chodziło Orientujesz się czy są jeszcze jakieś tego typu przydatne do wyrażeń regularnych?machina13 pisze:\(\displaystyle{ 10 ^{*} 10 ^{*} = 10 ^{*}}\)
-
- Użytkownik
- Posty: 73
- Rejestracja: 12 kwie 2009, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 16 razy
- Pomógł: 6 razy
[TPI] Wyrażenia regularne.
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ęć.
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
- Użytkownik
- Posty: 29
- Rejestracja: 9 kwie 2010, o 11:20
- Płeć: Mężczyzna
- Lokalizacja: Tychy
- Podziękował: 7 razy
- Pomógł: 2 razy
[TPI] Wyrażenia regularne.
Racja, po to mamy te domknięcia żeby tak tego nie rozpisywać:)Dzieki!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ęć.