In che modo la Gerarchia di Chomsky e le macchine di Turing influenzano il design del linguaggio?

Question

Attualmente sto studiando per un test di matematica discreto in cui stiamo imparando Chomsky's hierarchy e il tipo di macchine automatiche che riconoscono ogni livello della gerarchia. Mi viene insegnato che la maggior parte delle lingue informatiche rientrano nei "livelli 2 e 1" della gerarchia, ma non precisamente in che modo.

Le mie domande sono:

1. Quali caratteristiche appartengono a ogni livello?

2. Non è altro che una base teorica? Mi chiedo se i progettisti di linguaggi come Dennis Ritchie e James Gosling dovessero prendere in considerazione queste considerazioni quando progettano C e Java. Fanno? Come lo applicherebbe qualcuno?

3. Ci viene detto che Turing Machines riconosce il livello 0 della gerarchia. In tal caso, ci sono caratteristiche linguistiche che appartengono al livello 0? Immagino che questo possa essere un trattamento naturale del linguaggio, vero?

Answer 1

1. Nessuno. Livello 1 include Livello 2. Forse ho frainteso, in modo da essere completo:

   • Lingue regolari sono utilizzate all'interno di corrispondenza di espressioni regolari. Colloquiale: i DFA non possono contare. E devi contare se vuoi far corrispondere le parentesi. [Livello 3]
   • La sintassi della lingua è normalmente una lingua libera dal contesto. Vedere 2) [Livello 2]
   • Il linguaggio sensibile al contesto viene utilizzato solo in teoria. Vedi 3) [Livello 1]

2. Aiuta a progettare i lexer e parser. Non so se i creatori di C ci pensassero, ma Java, certamente. Parser Generator

3. Le macchine di turing calcolano tutto ciò che può essere calcolato. "Può essere calcolato" è anche definito come: può essere accettato da una macchina di Turing. Ciò include, naturalmente, l'elaborazione del linguaggio naturale. Qualsiasi cosa sopra il Livello 2 non è molto utile per la generazione della lingua, perché un programma che legge tali ingressi non può fermarsi (Word Problem non può più essere risolto).

Answer 2

Le grammatiche di tipo 3 generano lingue regolari. Queste sono lingue con caratteristiche come inizia con "xxx", contiene "xxx", termina con "xxx", contiene un numero dispari di y, ecc. Gli automi finiti (deterministici o non) riconoscono queste lingue.

Le grammatiche di tipo 2 generano lingue senza contesto. Queste sono lingue con caratteristiche come un certo numero di x seguite da un numero minore o uguale o uguale di y, o dove una parola è seguita dalla stessa parola, ma invertita. Gli automi pushdown riconoscono questi linguaggi ... pensate all'automa finito con uno stack.

Le grammatiche di tipo 1 generano lingue sensibili al contesto. Queste sono così vicine alle grammatiche di tipo 0 che è spesso difficile trovare una differenza tra loro. Gli LBA (automi lineari delimitati) riconoscono queste lingue, pensano che la macchina di Turing abbia risorse limitate ... pensa un computer moderno.

Le grammatiche di tipo 0 generano lingue di Turing, a volte denominate lingue ricorsivamente enumerabili. Questi sono praticamente tutti i linguaggi in cui è possibile scrivere un programma per computer da riconoscere, ma si fondono perfettamente con il Tipo 1, poiché i computer reali generalmente hanno un qualche tipo di limite di memoria.

Gli automi finiti e gli automi pushdown sono molto importanti per risolvere i problemi che sorgono durante la scrittura di compilatori. Tuttavia, non è per questo che li studi, li studi per imparare i limiti di ciò che può/non può essere calcolato. Molti programmatori pensano che sia possibile risolvere qualsiasi problema con un computer. La teoria della computabilità ti insegna diversamente.

modifica di "Dude" - OK, qui è un facile da capire (e famoso) problema che non può essere risolto da una qualsiasi macchina di Turing o computer o programmatore o genio alieno ...

Immaginate di avere alcuni domino ... ma invece di schemi di punti, hai una parola breve in alto e in basso, pronuncia parole come "aba" e "cab". Se ti do 5 o 10 o 50 di questi domino, puoi sistemarli in modo che le parole in alto, tutte concatenate insieme, corrispondano esattamente alle parole concatenate in basso. Puoi creare tutte le copie che vuoi di ogni e qualsiasi domino.

Esempio di domino (artificiale :) (a/aab), (aba/ac), (cabina/ab) è un insieme di 3 domino in cui le cime (a + aba + cabina) corrispondono esattamente al fondo (aab + ac + ab).

Per quanto facile possa sembrare, non può essere risolto in generale.

BTW, quando ho letto per la prima volta questo problema ... Stavo pensando ... ooooh, n! sta iniziando a guardare bene!