16 kontakty: Algorytm, Automat liniowo ograniczony, Automat ze stosem, Deterministyczny automat skończony, Gramatyka bezkontekstowa, Gramatyka formalna, Gramatyka kontekstowa, Język bezkontekstowy, Język formalny, Język kontekstowy, Język regularny, Język rekurencyjnie przeliczalny, Maszyna Turinga, Noam Chomsky, Postać normalna Chomsky’ego, Postać normalna Greibach.
Algorytm
Algorytm – skończony ciąg jasno zdefiniowanych czynności koniecznych do wykonania pewnego rodzaju zadań, sposób postępowania prowadzący do rozwiązania problemu.
Nowy!!: Hierarchia Chomsky’ego i Algorytm · Zobacz więcej »
Automat liniowo ograniczony
Automat liniowo ograniczony (ang. linear bounded automaton) – ograniczona wersja maszyny Turinga, która podczas obliczenia na słowie wejściowym długości n może wykorzystać jedynie O(n) komórek taśmy.
Nowy!!: Hierarchia Chomsky’ego i Automat liniowo ograniczony · Zobacz więcej »
Automat ze stosem
Przykładowy diagram automatu ze stosem Automat ze stosem (PDA) – automat skończony, który może dodatkowo korzystać ze stosu do przechowywania danych.
Nowy!!: Hierarchia Chomsky’ego i Automat ze stosem · Zobacz więcej »
Deterministyczny automat skończony
Deterministyczny automat skończony (ang. Deterministic Finite-state Automaton, DFA) to abstrakcyjna maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole pewnego słowa, po przeczytaniu każdego zmieniając swój stan na stan będący wartościąfunkcji jednego przeczytanego symbolu oraz stanu aktualnego.
Nowy!!: Hierarchia Chomsky’ego i Deterministyczny automat skończony · Zobacz więcej »
Gramatyka bezkontekstowa
Gramatyka bezkontekstowa – gramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń sąpostaci: gdzie: Każdy język bezkontekstowy generowany jest przez pewnągramatykę bezkontekstową.
Nowy!!: Hierarchia Chomsky’ego i Gramatyka bezkontekstowa · Zobacz więcej »
Gramatyka formalna
Gramatyka formalna – sposób opisu języka formalnego, czyli podzbioru zbioru wszystkich słów skończonej długości nad danym alfabetem.
Nowy!!: Hierarchia Chomsky’ego i Gramatyka formalna · Zobacz więcej »
Gramatyka kontekstowa
Gramatyka kontekstowa – gramatyka formalna, której reguły sąpostaci: gdzie: Każda gramatyka kontekstowa definiuje pewien język kontekstowy.
Nowy!!: Hierarchia Chomsky’ego i Gramatyka kontekstowa · Zobacz więcej »
Język bezkontekstowy
Język bezkontekstowy – język formalny taki, że istnieje niedeterministyczny automat ze stosem decydujący czy dany łańcuch należy do języka.
Nowy!!: Hierarchia Chomsky’ego i Język bezkontekstowy · Zobacz więcej »
Język formalny
Język formalny – podzbiór zbioru wszystkich słów nad skończonym alfabetem.
Nowy!!: Hierarchia Chomsky’ego i Język formalny · Zobacz więcej »
Język kontekstowy
Język kontekstowy (ang. context-sensitive language) – język formalny generowany przez gramatykę kontekstową.
Nowy!!: Hierarchia Chomsky’ego i Język kontekstowy · Zobacz więcej »
Język regularny
Język regularny – język formalny taki, że istnieje deterministyczny automat skończony potrafiący zdecydować, czy dane słowo należy do języka.
Nowy!!: Hierarchia Chomsky’ego i Język regularny · Zobacz więcej »
Język rekurencyjnie przeliczalny
Język rekurencyjnie przeliczalny (ang. recursively enumerable language) to język formalny określany jako język klasy 0 w hierarchii Chomsky’ego, który generowany jest przez gramatykę kombinatoryczną.
Nowy!!: Hierarchia Chomsky’ego i Język rekurencyjnie przeliczalny · Zobacz więcej »
Maszyna Turinga
Artystyczna wizja maszyny Turinga Maszyna Turinga – stworzony przez Alana Turinga abstrakcyjny model urządzenia służącego do wykonywania algorytmów.
Nowy!!: Hierarchia Chomsky’ego i Maszyna Turinga · Zobacz więcej »
Noam Chomsky
Noam Chomsky (ur. 7 grudnia 1928 w Filadelfii) – amerykański językoznawca, filozof, działacz polityczny.
Nowy!!: Hierarchia Chomsky’ego i Noam Chomsky · Zobacz więcej »
Postać normalna Chomsky’ego
Postać normalna Chomsky’ego to postać gramatyki bezkontekstowej, w której wszystkie reguły (inaczej: produkcje) sąpostaci: gdzie małe litery oznaczająsymbole terminalne, duże zaś nieterminalne.
Nowy!!: Hierarchia Chomsky’ego i Postać normalna Chomsky’ego · Zobacz więcej »
Postać normalna Greibach
Postać normalna Greibach to postać gramatyki bezkontekstowej, w której wszystkie reguły sąpostaci: gdzie a to dowolny symbol terminalny, Y_1...Y_m to (być może pusty) ciąg symboli nieterminalnych.
Nowy!!: Hierarchia Chomsky’ego i Postać normalna Greibach · Zobacz więcej »