Zbiór słów \(\displaystyle{ A \subseteq \left \{a, b \right\}^* }\) nazwiemy przekrojem, gdy:
(*) dla dowolnych różnych słów \(\displaystyle{ u, v \in A }\), słowo \(\displaystyle{ u}\) nie jest prefiksem \(\displaystyle{ v}\) ani \(\displaystyle{ v}\) nie jest prefiksem \(\displaystyle{ u}\);
(**) dla dowolnego słowa \(\displaystyle{ w \in \left\{ a,b\right\} ^*}\) istnieje takie słowo \(\displaystyle{ u \in A}\), że \(\displaystyle{ u}\) jest prefiksem \(\displaystyle{ w}\) lub \(\displaystyle{ w}\) jest prefiksem \(\displaystyle{ u}\).
Nie mogę zrozumieć, czy w takim przypadku przekrojem będzie tylko takie \(\displaystyle{ A = \{a,b\}}\)? bo jak weźmiemy jakieś większe słowo np. \(\displaystyle{ ab}\) to \(\displaystyle{ a}\) jest prefiksem \(\displaystyle{ ab}\)...
Więc \(\displaystyle{ A = \{a,b,ab\}}\) nie jest przekrojem, czy źle rozumiem?
Przekrój
-
- Administrator
- Posty: 34281
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Przekrój
Nie tylko. Np. zbiór \(\displaystyle{ \{a, ba, bb\}}\) też jest przekrojem.
Zgadza się, nie jest.
JK
-
- Użytkownik
- Posty: 99
- Rejestracja: 21 sty 2021, o 16:29
- Płeć: Kobieta
- wiek: 21
- Podziękował: 40 razy
Re: Przekrój
Dodano po 29 sekundach:
Czy jeśli \(\displaystyle{ A}\) jest przekrojem, to każdy maksymalny łańcuch w \(\displaystyle{ \left\{ a,b \right\}^
* }\) z porządkiem prefiksowym ma niepuste przecięcie z \(\displaystyle{ A}\)?
Czy mogłabym poprosić Pana o jakieś wskazówce jak za to zabrać się?
Bo mam takie zadanie:Jan Kraszewski pisze: ↑17 gru 2021, o 20:13Nie tylko. Np. zbiór \(\displaystyle{ \{a, ba, bb\}}\) też jest przekrojem.
Zgadza się, nie jest.
JK
Czy jeśli \(\displaystyle{ A}\) jest przekrojem, to każdy maksymalny łańcuch w \(\displaystyle{ \left\{ a,b \right\}^
* }\) z porządkiem prefiksowym ma niepuste przecięcie z \(\displaystyle{ A}\)?
Czy mogłabym poprosić Pana o jakieś wskazówce jak za to zabrać się?
Ostatnio zmieniony 17 gru 2021, o 21:06 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Administrator
- Posty: 34281
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Przekrój
O \(\displaystyle{ \left\{ a,b \right\}^* }\) z porządkiem prefiksowym możesz myśleć jak o drzewie binarnym. Wtedy maksymalny łańcuch odpowiada (nieskończonej) gałęzi w tym drzewie, natomiast przekroje to w pewnym sensie poziomy w tym drzewie (dokładniej, każdy poziom jest przekrojem, ale nie każdy przekrój jest poziomem). Ściśle - przekroje to maksymalne antyłańcuchy w tym porządku. Zatem przekroje rozciągają się od lewego do prawego końca drzewa, a maksymalne łańcuchy ciągną się od samego dołu do samej góry tego drzewa. Wobec tego muszą się przeciąć.
Dowód jest natychmiastowy. Ustal przekrój \(\displaystyle{ A}\) i maksymalny łańcuch \(\displaystyle{ L}\). Ustal dowolny element \(\displaystyle{ l\in L}\). Ponieważ \(\displaystyle{ A}\) jest przekrojem, więc z (**) istnieje \(\displaystyle{ v\in A}\), które jest porównywalne z \(\displaystyle{ l}\). Ale skoro \(\displaystyle{ v}\) i \(\displaystyle{ l}\) są porównywalne, to z maksymalności łańcucha \(\displaystyle{ L}\) wynika (dlaczego? - musisz uzasadnić, że \(\displaystyle{ v}\) jest porównywalne ze wszystkimi elementami \(\displaystyle{ L}\)), że \(\displaystyle{ v\in L}\), czyli \(\displaystyle{ v\in A\cap L}\), co kończy dowód.
JK
-
- Użytkownik
- Posty: 99
- Rejestracja: 21 sty 2021, o 16:29
- Płeć: Kobieta
- wiek: 21
- Podziękował: 40 razy
Re: Przekrój
Jan Kraszewski pisze: ↑17 gru 2021, o 21:51O \(\displaystyle{ \left\{ a,b \right\}^* }\) z porządkiem prefiksowym możesz myśleć jak o drzewie binarnym. Wtedy maksymalny łańcuch odpowiada (nieskończonej) gałęzi w tym drzewie, natomiast przekroje to w pewnym sensie poziomy w tym drzewie (dokładniej, każdy poziom jest przekrojem, ale nie każdy przekrój jest poziomem). Ściśle - przekroje to maksymalne antyłańcuchy w tym porządku. Zatem przekroje rozciągają się od lewego do prawego końca drzewa, a maksymalne łańcuchy ciągną się od samego dołu do samej góry tego drzewa. Wobec tego muszą się przeciąć.
Dowód jest natychmiastowy. Ustal przekrój \(\displaystyle{ A}\) i maksymalny łańcuch \(\displaystyle{ L}\). Ustal dowolny element \(\displaystyle{ l\in L}\). Ponieważ \(\displaystyle{ A}\) jest przekrojem, więc z (**) istnieje \(\displaystyle{ v\in A}\), które jest porównywalne z \(\displaystyle{ l}\). Ale skoro \(\displaystyle{ v}\) i \(\displaystyle{ l}\) są porównywalne, to z maksymalności łańcucha \(\displaystyle{ L}\) wynika (dlaczego? - musisz uzasadnić, że \(\displaystyle{ v}\) jest porównywalne ze wszystkimi elementami \(\displaystyle{ L}\)), że \(\displaystyle{ v\in L}\), czyli \(\displaystyle{ v\in A\cap L}\), co kończy dowód.
JK
Dziękuję bardzo za pomoc!
- Dasio11
- Moderator
- Posty: 10225
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: Przekrój
Otóż nie musi mieć! - mam świadka:
\(\displaystyle{ A = \{ a^nb : n \in \NN \}, L = \{ a^n : n \in \NN \}}\)
-
- Administrator
- Posty: 34281
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Przekrój
Masz rację, zbyt optymistycznie byłem nastawiony do tego fragmentu dowodu:
JK
Swoją drogą to podstępny przykład - przekrój z jednej strony wygina się do góry, a łańcuch wciska się w powstałą szczelinę...Jan Kraszewski pisze: ↑17 gru 2021, o 21:51musisz uzasadnić, że \(\displaystyle{ v}\) jest porównywalne ze wszystkimi elementami \(\displaystyle{ L}\)
JK