Teoria de la Computació: Llenguatges i Complexitat
Lema de bombeig per a llenguatges regulars
Llenguatge Multi-full: L = {(a³b²)ᵏ | k > 0}
- 1. Assumim que és regular.
- 2. p serà la longitud de bombeig // S = (a³b²)ᵖ.
- 3. S té almenys una longitud p.
- 4. Partim s de la següent manera: x = ε, y = (a³b²), z = ε.
Condicions:
- Condició 1: Per a cada i ≥ 0, xyⁱz ∈ A (D'acord).
- Condició 2: |y| > 0 (D'acord).
- Condició 3: |xy| ≤ p (D'acord).
Tancament de la classe de llenguatges regulars
Demostreu que la classe dels llenguatges regulars és tancada sota l'operació de concatenació:
Fem dos NFA, un per a A₁ i un per a A₂, i els combinem en un nou NFA N. L'inici de N serà l'inici de N₁. Si N₁ es troba en un estat d'acceptació, significa que ha trobat una peça inicial de l'entrada...