Dlaczego zwykły język nazywa się „zwykłym”?

Właśnie zakończyła pierwszy rozdział Wprowadzenie do teorii obliczeń przez Michaela Sipser który wyjaśnia podstawy automatów skończonych.

Definiuje zwykły język jako wszystko, co można opisać za pomocą automatów skończonych. Ale nie mogłem znaleźć, gdzie tłumaczy, dlaczego zwykły język nazywa się „zwykłym”. Jakie jest pochodzenie terminu „regularny” w tym kontekście?

UWAGA: Jestem nowicjuszem, więc spróbuj wyjaśnić w prosty sposób!

Jak powiedział Kaveh w komentarzu, Kleene obdarzył to imię w przeszłości, kiedy rozpoczął teorię automatów i języki formalne. Uważam, że termin ten był dowolny, choć minęło wiele lat, odkąd przeczytałem jego oryginalny artykuł.

Matematycy mają zwyczaj przejmowania wspólnych rzeczowników i przymiotników dla obiektów i właściwości matematycznych, czasem z dobrych powodów, takich jak geometryczne lub inne analogie lub metafory, a czasem arbitralnie. Wystarczy spojrzeć na „grupę”, „pierścień”, „przestrzeń”, „snop”, „atlas”, „rozmaitość”, „pole” i tak dalej.

W rzeczywistości termin „regularny” dla języków o stanie skończonym, choć nadal powszechny w teorii automatów, nie jest zbyt często używany w jego kuzynie algebraicznym, teorii półgrup skończonych lub algebrze abstrakcyjnej w ogóle. Czemu? Ponieważ termin został już przyjęty dla półgrupy, która jest zbliżona do grupy w konkretnym sensie technicznym, więc nie można było dopasować zwykłego języka w sensie Kleene do odpowiedniej regularnej półgrupy . Po trzecie, Kleene zdefiniowała inny rodzaj wydarzenia o nazwie „definite”, który był przez pewien czas badany, ale okazał się niezbyt owocny. Dziś skończone zestawy języka odgrywają rolę określonych zdarzeń jako podstawa regularnych wydarzeń.

Preferowany termin w algebrze jest „racjonalny” zarówno dla klasy języków Kleene'a, jak i dla bardziej ogólnych półgrup i monoidów. Użycie to odzwierciedla także ważną analogię między terminem „wymiernym” w algebrze jako rozwiązaniem równania liniowego o współczynnikach całkowitych a koncepcją szeregów wymiernych mocy w automatach i teorii języka formalnego.

Dodatkowe informacje. Oryginalną pracę Kleene z 1951 r. Zatytułowaną „Reprezentacja wydarzeń w sieciach nerwowych i automatach skończonych” można znaleźć tutaj . Na str. 46 ustala arbitralność terminu „regularny” za pomocą tego oświadczenia:

Obecnie opiszemy klasę wydarzeń, które nazwiemy „zwykłymi wydarzeniami”. (Chętnie przyjmiemy wszelkie sugestie dotyczące bardziej opisowego terminu).

Najwyraźniej nikt nie wymyślił bardziej opisowego terminu. ;-)

Jak to często bywa w przypadku przełomowych prac, które prowadzą do intensywnego rozwoju całych nowych obszarów, terminologia i koncepcje są prawie nie do poznania w dzisiejszych terminach. Po pierwsze, artykuł dotyczył modeli neuronów, stąd użycie „zdarzeń” zamiast „języków” lub „zestawów”. Termin „wydarzenia” przetrwał również w latach 60. i 70., nawet pomimo tego, że znaczenie koncepcji Kleene dla automatów i języków formalnych znacznie przewyższyło jakąkolwiek wartość dla neuronauki.

Po drugie, istnieją pewne matematyczne różnice, takie jak zdefiniowanie tak zwanej „Zamknięcia Kleene” jako operacji binarnej, równoważnej , zamiast prostszej operacji jednoargumentowej lub , której używamy dzisiaj. Motywacją Kleene było uniknięcie pustej struny (lub zdarzenia o jego długości zero). To była niezwykle przewidywalna intuicja, ponieważ późniejsza teoria pokazała, jak decydujący jest wybór włączenia lub wyłączenia pustego ciągu z definicji w wielu kontekstach. Po trzecie, Kleene zdefiniowała koncepcję zwaną „zdarzeniami określonymi” i opracowała z nich regularne zdarzenia, ale obecnie do tego celu używamy zbiorów skończonych. Zdecydowane wydarzenia były przez jakiś czas badane, ale okazały się o wiele mniej ważne niż zwykłe wydarzenia / zestawy / języki.$a^*b$$a^*$$a^+$

Zresztą pełne czytanie tego artykułu prawdopodobnie nie jest dziś warte niczyjego czasu, z wyjątkiem celów historycznych. Właśnie przejrzałem go w poszukiwaniu kluczowych definicji i pomysłów, i było to zabawne.

Zawsze rozumiałem termin „regularny”, co oznacza, że ​​opiera się na powtarzającym się schemacie. Po wyliczeniu wszystkich łańcuchów określonej długości zobaczyłeś je wszystkie. Potem nie będzie już nic nowego.

(To oczywiście tylko niejasna intuicja).