Alfabet ;) lw: Witam. Czytam sobie Matematyke Dyskretna Rossa i Wrighta i na stronie 22 jest napisane, ze "Jesli ∑ zawiera ab, aba, bab to ciąg wejściowy ababab może być zinterpretowany albo jako (ab)(ab)(ab) albo jako (aba)(bab). Aby uniknąc takich problemów, nie pozwolimy, by zbiór ∑ zawierał jakiekolwiek litery, które same są ciągami liter rozpoczynającymi się od litery należącej do ∑. Zatem dopuścimy zbiory ∑ = {a,b,c} (...) ale nie dospuścimy ani ∑ = {a,b,c,ac}, ani nawet ∑ = {a, b, ac} Przedostatni zbior rozumiem. Dla ∑ = {a,b,c,ac} do ∑* należałoby {ac, ac} i nie byłoby wiadomo jak to zinterpretować. Natomiast jaki jest problem z tym ostatnim epsilonem? Tzn, ∑ = {a, b, ac}.?

Trivial: ∑ to sigma (wielka), a nie epsilon. http://pl.wikipedia.org/wiki/Alfabet_grecki#Klasyczne_litery_greckie > Aby uniknąc takich problemów, nie pozwolimy, by zbiór ∑ zawierał jakiekolwiek litery, > które same są ciągami liter rozpoczynającymi się od litery należącej do ∑. ac rozpoczyna się od a∊∑. Na upartego można by na takie coś pozwolić, ale strasznie skomplikuje to odpowiedzi nawet na najprostsze pytania.

lw: A, przepraszam, ∑ to rzeczywiscie sigma a nie epsilon.

lw: Ok, a moglbys prosze podac jakis w miare prosty przyklad kiedy by to sprawe skompilikowalo?

Trivial: Niech ∑ = { a, b, aaabaacaab }. Czy łańcuch aaabaacaabaaabbaabaacabaacaabaaaabaacaab da się zapisać korzystając z alfabetu ∑? Żeby to stwierdzić nie wystarczy "iść po kolei" i sprawdzać czy każdy ciąg znajduje się w ∑.

Trivial: Dla porównania odpowiedź na takie samo pytanie przy ∑ = { a, b, caaabaaaab } jest już bardzo prosta. a a a b a a caa baaabbaabaacabaacaabaaaabaacaab ^ błąd