Witam
Mam problem z ponizszym zadaniem:
Niech A będzie pewnym alfabetem. Dla \(\displaystyle{ w_1 , w_2 \in A^*}\) (A*, to zbiór słów nad alfabetem A) powiemy, że \(\displaystyle{ w_1\ r\ w_2}\), jeśli w A* istnieją słowa w i w’ takie, że \(\displaystyle{ w_2 = ww_1 w'}\). Czy r jest częściowym porządkiem w zbiorze A*?
Z góry dziękuje za pomoc
Pozdrawiam
częściowy porządek
-
wjzz
- Użytkownik
- Posty: 70
- Rejestracja: 24 lut 2007, o 16:06
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 18 razy
częściowy porządek
Wychodzi mi, że tak.
(Oznaczam słowo puste przez \(\displaystyle{ \epsilon}\).)
Dowód: Musimy sprawdzić czy relacja R jest:
1. Zwrotna: Tak, bo dla dowolnego słowa w mamy: \(\displaystyle{ w = \epsilon w \epsilon}\), czyli \(\displaystyle{ w R w}\)
2. (Słabo) antysymetryczna: Niech \(\displaystyle{ w_1\ R\ w_2}\) oraz \(\displaystyle{ w_2\ R\ w_1}\). Pokażemy, że wtedy \(\displaystyle{ w_1 = w_2}\).
Z definicji naszej relacji znajdziemy słowa \(\displaystyle{ a,b,c,d}\) takie, że \(\displaystyle{ w_2 = aw_1b}\) oraz \(\displaystyle{ w_1 = cw_2d}\). W takim razie \(\displaystyle{ w_1 = c(aw_1b)d = (ca)w_1(bd)}\). Żeby dwa słowa były równe to przede wszystkim muszą mieć równą długość. Jeżeli któreś ze słow \(\displaystyle{ a,b,c,d}\) nie jest słowem pustym, to długość słowa \(\displaystyle{ caw_1bd}\) jest ostro większa od słowa \(\displaystyle{ w_1}\), więc równość nie zachodzi. Wnosimy stąd, że musi być \(\displaystyle{ a = b = c = d = \epsilon}\). Skoro powiedzieliśmy wcześniej, że \(\displaystyle{ w_2 = aw_1b}\), to na mocy ostatniej dowiedzionej równości mamy, że \(\displaystyle{ w_1 = w_2}\). Zatem istotnie R jest słabo antysymetryczna.
3. Przechodnia: Niech \(\displaystyle{ w_1\ R\ w_2}\) oraz \(\displaystyle{ w_2\ R\ w_3}\). Rozpisując z definicji mamy, że (dla pewnych słów a,b,c,d): \(\displaystyle{ w_2 = aw_1b}\) oraz \(\displaystyle{ w_3 = cw_2d}\). Zatem \(\displaystyle{ w_3 = c(aw_1b)d = (ca)w_1(bd)}\). Jako, że ca oraz bd również są słowami, to pokazaliśmy, że \(\displaystyle{ w_1\ R\ w_3}\).
Skoro relacja R jest zwrotna, (słabo) antysymetryczna i przechodnia to R jest częściowym porządkiem.
(Oznaczam słowo puste przez \(\displaystyle{ \epsilon}\).)
Dowód: Musimy sprawdzić czy relacja R jest:
1. Zwrotna: Tak, bo dla dowolnego słowa w mamy: \(\displaystyle{ w = \epsilon w \epsilon}\), czyli \(\displaystyle{ w R w}\)
2. (Słabo) antysymetryczna: Niech \(\displaystyle{ w_1\ R\ w_2}\) oraz \(\displaystyle{ w_2\ R\ w_1}\). Pokażemy, że wtedy \(\displaystyle{ w_1 = w_2}\).
Z definicji naszej relacji znajdziemy słowa \(\displaystyle{ a,b,c,d}\) takie, że \(\displaystyle{ w_2 = aw_1b}\) oraz \(\displaystyle{ w_1 = cw_2d}\). W takim razie \(\displaystyle{ w_1 = c(aw_1b)d = (ca)w_1(bd)}\). Żeby dwa słowa były równe to przede wszystkim muszą mieć równą długość. Jeżeli któreś ze słow \(\displaystyle{ a,b,c,d}\) nie jest słowem pustym, to długość słowa \(\displaystyle{ caw_1bd}\) jest ostro większa od słowa \(\displaystyle{ w_1}\), więc równość nie zachodzi. Wnosimy stąd, że musi być \(\displaystyle{ a = b = c = d = \epsilon}\). Skoro powiedzieliśmy wcześniej, że \(\displaystyle{ w_2 = aw_1b}\), to na mocy ostatniej dowiedzionej równości mamy, że \(\displaystyle{ w_1 = w_2}\). Zatem istotnie R jest słabo antysymetryczna.
3. Przechodnia: Niech \(\displaystyle{ w_1\ R\ w_2}\) oraz \(\displaystyle{ w_2\ R\ w_3}\). Rozpisując z definicji mamy, że (dla pewnych słów a,b,c,d): \(\displaystyle{ w_2 = aw_1b}\) oraz \(\displaystyle{ w_3 = cw_2d}\). Zatem \(\displaystyle{ w_3 = c(aw_1b)d = (ca)w_1(bd)}\). Jako, że ca oraz bd również są słowami, to pokazaliśmy, że \(\displaystyle{ w_1\ R\ w_3}\).
Skoro relacja R jest zwrotna, (słabo) antysymetryczna i przechodnia to R jest częściowym porządkiem.