È possibile creare una lingua normale da una lingua non regolare?

Question

È possibile creare una lingua normale da una lingua non regolare?

#1 da (6 voti)

1

Mi chiedo se sia possibile creare una lingua normale da una lingua irregolare se aggiungiamo o rimuoviamo un numero finito di parole da essa?

Dite che L è irregolare, possiamo aggiungere o rimuovere un numero finito di parole per creare un linguaggio normale?

potrei sbagliarmi, ma dato che tutti i linguaggi regolari sono finiti - se aggiungiamo una quantità finita a una lingua non regolare - rimane non regolare, ma se sottragiamo, diciamo una quantità finita dall'infinito, è ancora infinito.

quindi è sicuro dire che in entrambi i casi non è possibile ottenere una lingua normale aggiungendo / sottostrando una quantità limitata di parole?

regular-expressions languages automata

posta mathnoobie 02.12.2018 - 14:49

fonte

1 risposta

Leggi altre domande sui tag regular-expressions languages automata

Utilizzo di "On" all'inizio del nome di un metodo Come devo implementare le funzioni utilizzate per lo stesso scopo quando si utilizza il modello di progettazione della strategia?

score 6 · Accepted Answer

Le lingue finite sono banalmente enumerabili solo elencando i loro membri, e quindi più deboli delle normali lingue. Quindi l'intera gerarchia dei linguaggi formali riguarda solo lingue infinite, e ogni lingua superiore è infinita in un modo qualitativamente nuovo . Ad esempio, le lingue regolari non possono contare le cose, ma le lingue libere dal contesto possono.

Nessuna di queste differenze può essere superata aggiungendo un numero finito di elementi, quindi sì, né l'aggiunta né la rimozione possono spostarsi tra normali e non regolari.