Кіріспе

Формалды тілді танитын ең кішкентай моноид. Математика мен компьютерлік ғылымда формалды тілдің синтаксистік моноиді – сол тілді танитын ең кішкентай моноид болып табылады.

Михилл-Нерод теоремасы

Милхилл-Нерод теоремасы былай глайды: тіл егер және тек қана үлестірмелер жинағы шекті болса, немесе сол жақ синтаксистік эквиваленттіліктің шекті индексі болса (яғни, ол тілді шекті сандағы эквиваленттілік кластарына бөледі) тұрақты болады. Бұл теорема алғаш рет Анил Неродпен дәлелденген, сондықтан кейбір авторлар бұл қатынасты Нерод конгруенциясы деп атайды.

Дәлел

"Егер ғана" бөлігінің дәлелі келесідей: Шешімді автоматты тану үшін кіріс тізбегін оқиды деп есептейік, нәтижесінде машина күйіне жетеді. Егер машина басқа тізбекті оқыса, ол да сол күйде аяқталады, онда бұл анық. Сондықтан, жинақтың элементтерінің саны автоматтың күйлерінің санынан артық болмайды, ал жинақтың саны автоматтың соңғы күйлерінің санынан артық болмайды. "Егер" бөлігінің дәлелі үшін жинақтың элементтерінің саны шекті деп есептейік. Одан кейін, автоматты құруға болады, онда жинақ күйлер жиынтығы, жинақ соңғы күйлер жиынтығы, тіл бастапқы күй болады, ал көшу функциясы былай беріледі. Анық айтқанда, бұл автоматті таниды.

Осылайша, тіл танылатындығы жинақтың шекті болуымен шартталған. Бұл дәлел минималды автоматты да құрастырады.

Мысалдар

Тіл жұп ұзындықтағы сөздер жиыны болсын. Синтаксистік конгруэнцияның екі класы бар: өзі және , тақ ұзындықтағы сөздер. Синтаксистік моноид – тіл үшін минималды автоматтың 4 күйі бар, ал синтаксистік моноид 15 элементтен тұрады. Бициклді моноид – Дик тілінің (баланстелген жақшалар тілінің) синтаксистік моноиды. (мұнда ) бос моноид – тілдің синтаксистік моноиды , мұнда – сөздің кері тілі (мысалы, әріптің квадраттық дәрежелерінің тілін пайдалануға болады). Кез келген тривиалды емес шекті моноид, кейбір тривиалды емес тілдің синтаксистік моноидына гомоморфты, бірақ кез келген шекті моноид синтаксистік моноидқа изоморфты емес. Кез келген шекті топ, кейбір реттелген тілдің синтаксистік моноидына изоморфты. Жұлдызсыз тілдер, шекті апериодты синтаксистік моноидтармен сипатталады.