Perché {a^nb^n | n> = 0} non regolare?

In un corso di CS che non vi sto prendendo è un esempio di un linguaggio che non è regolare:Perché {a^nb^n | n> = 0} non regolare?

{a^nb^n | n >= 0}

posso capire che non è regolare in quanto non Finite State Automaton/macchina può essere scritto che convalida e accetta questo input poiché manca un componente di memoria. (Si prega di correggermi se ho torto)

Il wikipedia entry on Regular Language elenca anche questo esempio, ma non fornisce una prova (matematica) del perché non è regolare.

Qualcuno mi può illuminare su questo e fornire una prova per questo, o indicare anche me una buona risorsa?

fonte

2010-02-22 Christophe Herreman

Quello che stai cercando è Pumping lemma for regular languages.

Ecco un example con il tuo problema esatto:

Esempi:
Sia L = {a ^m b ^m | m ≥ 1}.
Quindi L non è regolare.
Dimostrazione: Sia n come in Pump Lemma.
Let w = a ⁿ b ⁿ.
Sia w = xyz come in Pump Lemma.
Quindi, xy z ∈ L, tuttavia, xy z contiene più a di b.

fonte

2010-02-22 08:53:54 cletus

Grazie, proprio quello che stavo cercando. –

l'ultima richiesta richiede spiegazioni migliori. La parola x2yz potrebbe contenere più lettere di un tipo (se y ha più di a che b o vice versa), o duplicarla manderebbe in frantumi l'ordine delle lettere, in cui b dovrebbe venire dopo tutte le a. –

prova incompleta. non hai definito x, y, z. x ha solo la limitazione che | xy | <= p, dove p è la lunghezza di pompaggio. devi dividere la prova in tre casi, con le stringhe y basate su (a | ab | b) perché sia completa. xy potrebbe consistere di più di b: a: x = a, y = b^n, z = b – oligofren

Poiché non è possibile scrivere una macchina a stati finiti che "conterrà" sequenze identiche di simboli "a" e "b". In poche parole, le FSM non possono "contare". Prova a immaginare un FSM: quanti stati daresti al simbolo "a"? Quanti a "b"? Cosa succede se la sequenza di input ha di più?

Si noti che se si dispone di n < = X con X un valore intero è possibile preparare tale FSM (avendo uno con un sacco di stati, ma ancora un numero finito); tale linguaggio sarebbe regolare.

fonte

2010-02-22 08:56:56 lorenzog

L'Automa a stati finiti non ha struttura dati (stack) - memoria come nel caso dell'automa push down. Sì, può darti un "a" seguito da alcune "b" ma non una quantità esatta di "a" seguita da "no" b ".

fonte

2015-02-26 06:16:25

Perché {a^nb^n | n> = 0} non regolare?

risposta

Problemi correlati