È L = {a^n b^m | n> m} una lingua regolare o irregolare?

Question

Ho difficoltà a risolvere/dimostrare questo problema. Qualche idea per favore?

Answer 1

L = {a ⁿ b ^m | n> m} è non lingua normale.

Sì, il problema è difficile in un primo tentativo e pochi meritano voto-up.

Il Lemma di pompaggio una proprietà necessaria del linguaggio normale è uno strumento per la dimostrazione formale che la lingua non è una lingua normale.

definizione formale: Pumping lemma for regular languages

Let L essere un linguaggio regolare. Quindi esiste un intero p ≥ 1 dipende solo L tale che ogni stringaw in L di lunghezza almeno p (p è chiamata la "lunghezza pompaggio") può essere scritte come w =xyz (vale a dire, w può essere diviso in tre sotto-stringhe), che soddisfano le seguenti condizioni:

1. | y | ≥ 1
2. | xy | ≤ p
3. per tutti i ≥ 0, xy ⁱ z ∈ L

Supponiamo, se si sceglie stringa W = a ⁿ b ^m dove (n + m) ≥ p e n > m + 1. La scelta di W è valida ma questa scelta non è possibile per mostrare che la lingua è non lingua normale. Perché con questo W avete sempre at-almeno una scelta di y=a per pompare nuove stringhe in lingua ripetendo a per tutti valori di i(per i = 0 e i> 1) .

Prima di scrivere la soluzione per provare la lingua non è regolare.Si prega di comprendere i seguenti punti e avviso: ho reso in grassetto every string w e all i nella definizione formale di lemma di pompaggio sopra.

• Anche se con un po 'Sufficiently large W in un linguaggio si è in grado di generare nuova stringa nel linguaggio ma NON possibile con tutti! Ci sono molte scelte possibili per W (di seguito nella mia prova) con che non si può trovare alcuna scelta di y per generare nuova stringa nel linguaggio per tutti i> = 0. Quindi, poiché ogni Sufficiently large W non è in grado di generare una nuova stringa nella lingua, quindi la lingua è NON regolare.

lettura: what pumping lemma formal definition says

Prova: usando pumping lemma

Fase (1): Scegliere stringa W = a ⁿ b ^m dove (n + m) ≥ p e n = m + 1.

Is this choice ofWis valid according to pumping lemma?

Sì, come ad W è in lingua perché il numero di a = n > numero di b = m. W è in lingua e sufficientemente grande> = p.

Passo (2): Ora ha scelto un y per generare nuova stringa per tuttoi >= 0.

E no la scelta è possibile per y questa volta! Perché?

primo, è saggio per capire che non possiamo avere b simbolo y perché sarà o generare nuove stringhe su modello o in stringa risultante numero totale di b volontà essere più del numero totale di a simboli.

In secondo luogo, non possiamo abbiamo scelto y = alcuni una s' perché con i=0 si otterrebbe una nuova stringa in cui il numero di a s sarà inferiore a numero b s che non è possibile in linguaggio. (ricordare il numero di a in W è solo più quindi b quindi rimuovendo qualsiasi mezzo nella stringa risultante n (a) = n (b) che non è accettabile perché n> m)

Quindi potremmo trovare alcuni W che sono sufficientemente grandi ma usando non possiamo generare una nuova stringa in linguaggio che contraddica pompando la proprietà del lemma del linguaggio regolare quindi il linguaggio {a ⁿ b ^m | n> m} è non un linguaggio normale in effetti.