Alfabet czy nie alfabet?

[rNest]

Proszę o sprawdzenie:

Które z podanych zbiorów są alfabetami:

\(\displaystyle{ a) \sum_{}^{} =\left\{ ab,ba,abc\right\}, b) \sum_{}^{} = \left\{ x \in N: x^{2}+x=0\right\},c) \sum_{}^{} = \left\{ ab,1,2\right\},d) \sum_{}^{} = Z.}\)

a) nie jest alfabetem - trzeci element zaczyna się na tą samą literę co pierwszy,
b) nie jest alfabetem - nie ma liczby naturalnej, która spełni to równanie,
c) jest alfabetem,
d) nie jest alfabetem - do liczb całkowitych zalicza się np. 1, 11, 111, zatem zaczynają się od tej samej litery.

Wypisz wszystkie słowa długości 2 w zbiorach będących alfabetami.

Zatem tylko c) jest alfabetem: \(\displaystyle{ \left\{ ab1,ab2,12,21,1ab,2ab\right\}}\) .

Czy powyższe jest prawidłowe?

[bartek118]

Nie do końca rozumiem, co to znaczy że zbiór jest alfabetem dla Ciebie. Dla mnie alfabet to dowolny zbiór skończony niepusty, więc tylko d i b nie ą alfabetami. Nie widzę powodu żeby np. a nie było alfabetem. Elementami alfabetu są litery, nie możemy więc rozpatrywać, że dwie litery zaczynają się tym samym, traktujemy je jako całość.

[rNest]

Jest założenie, że w alfabecie żadna litera nie może się zaczynać od już istniejącej.
Toteż a) odpada. Chyba.

[norwimaj]

Zatem zdefiniuj, co to jest alfabet, żebyśmy wiedzieli, o czym mówimy. Dla mnie alfabet to dowolny zbiór, zwykle skończony.

[rNest]

Definicja, za Rossem i Wrightem("Matematyka dyskretna"):
""... Po pierwsze, powiemy, że alfabet jest to skończony zbiór niepusty ... , którego elementami są symbole, często nazywane literami ... ",
oraz:
"...Aby uniknąć takich problemów, nie pozwolimy na to, by zbiór sigma zawierał jakiekolwiek litery, które same są ciągiem liter rozpoczynającymi się od litery należącej do sigma."

Zacytowałem dość dokładnie.

[norwimaj]

Dosyć mętne to, więc trudno o jednoznaczną odpowiedź. Używanie słowa "litera" w dwóch znaczeniach jest mylące. Dlatego poniżej będę pisał o literach i literkach.

Moim zdaniem, jeśli \(\displaystyle{ abc}\) jest ciągiem literek, to jest to trójelementowy ciąg \(\displaystyle{ (a,b,c)}\). Ciąg ten rozpoczyna się od \(\displaystyle{ a}\), które nie należy do \(\displaystyle{ \Sigma}\), więc nie ma przeszkody w tym, aby obie litery: \(\displaystyle{ ab}\) i \(\displaystyle{ abc}\) należały do \(\displaystyle{ \Sigma}\). Jednak może też chodzić o co innego.

Być może chodzi o to, żeby żadna litera nie była właściwym prefiksem innej litery, czyli mówiąc inaczej, aby \(\displaystyle{ \Sigma}\) był kodem bezprefiksowym. Wtedy \(\displaystyle{ ab}\) i \(\displaystyle{ abc}\) nie mogą być jednocześnie literami. Zatem \(\displaystyle{ \Sigma}\) z punktu a) nie jest alfabetem w sensie powyższej definicji. Chociaż skądinąd wiadomo, że \(\displaystyle{ \Sigma}\) jest kodem, czyli nie ma problemu z jednoznacznym odczytaniem.

[bartek118]

Formalnie, jeśli \(\displaystyle{ \Sigma}\) jest alfabetem i \(\displaystyle{ abc \in \Sigma}\), to jest to jedna litera. Nie rozbijamy tego na drobniejsze elementy jak te Twoje "literki", to jest jeden obiekt, dla którego użyłeś właśnie takiego oznaczenia i tyle. Zgodnie z Twoim cytatem - dla wygody raczej nie stosuje się takich oznaczeń, ponieważ trudniej będzie odczytać słowo nad takim alfabetem. Ale formalnie w niczym to nie przeszkadza, to jest tylko oznaczenie litery, zgodnie z definicją Rossa i Wrighta alfabet to niepusty zbiór skończony i tego trzeba się trzymać.