Konkatenering af regulære sprog

Vi har to regulære sprog L₁, L₂. Vi viser, at deres konkatenering L = L₁ ∘ L₂ også er et regulært sprog.

Hvad er konkatenering

Ved at konkatenere to ord »010« og »1111« opstår ordet »0101111«. Ved konkatenering af sprog opstår der altså et nyt sprog, som vi konstruerer ved at konkatenere hvert ord fra det ene sprog med hvert ord fra det andet sprog. Konkatenering af to ord og af to sprog betegner vi med en bolle: ∘. Så kan vi definere konkatenering af sprogene L₁ og L₂ således:

$$L_1\circ L_2=\{a\circ b|a\in L_1,b\in L_2\}$$

Idéen bag beviset

Vi har to regulære sprog L₁, L₂ og to automater, som accepterer disse sprog:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Vi konstruerer en ikke-deterministisk automat A = ⟨Q, Σ, δ, q, F⟩, som »indeholder« begge automater A₁ og A₂. Grundidéen er, at vi begynder at acceptere ordet med automaten A₁, og når automaten A₁ når til en accepttilstand, forsøger vi at lade automaten A₂ acceptere den resterende del af ordet. Hvis også denne automat accepterer den del af ordet, accepterer automaten A ordet.

Eksempel

Vi ser på denne automat A₁, som accepterer ikke-tomme ord bestående kun af nuller og ord bestående af et ettal efterfulgt af kun nuller (1, 10, 100, …):

og desuden denne automat A₂, som accepterer ord, der ender på 01:

Vi forbinder automaterne ved fra alle accepttilstande i automaten A₁ at tilføje epsilon-overgange til starttilstanden i automaten A₂ og derefter gøre accepttilstandene i A₁ til almindelige tilstande. Starttilstanden i hele den nye automat bliver starttilstanden i automaten A₁:

Hvordan vil automaten fungere? Vi begynder at simulere automaten A₁. Hvis vi går over til den tidligere accepttilstand q₁ eller q₂, ved vi, at automaten A₁ accepterer en del af dette ord. For at hele ordet skal være en del af sproget L₁ ∘ L₂, skal den resterende del af ordet accepteres af den anden automat A₂ — derfor fører der epsilon-overgange fra alle de tidligere accepttilstande til den oprindelige starttilstand i automaten A₂.

Lad os som eksempel tage ordet 0001. Det hører til konkateneringen af begge sprog, for ordet kan opstå ved konkatenering af ordene 00 ∘ 01. Men det kan lige så godt opstå ved konkatenering af ordene 0 ∘ 001. I vores automat kan vi simulere begge fremgangsmåder. Automaten kan gå denne vej:

$$q_0{\to }^0{q}_1{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

Ad denne vej ville automaten først »acceptere« delen 00 af ordet og derefter delen 01. Eller den kan gå denne vej:

$$q_0{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

og automaten ville så først »acceptere« delen 0 af ordet og derefter delen 001. I begge tilfælde ender vi naturligvis i accepttilstanden p₂.

Formel fremgangsmåde

Endnu en gang: Vi har to regulære sprog L₁, L₂ og to automater, som accepterer disse sprog:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Vi konstruerer en ikke-deterministisk automat A = ⟨Q, Σ, δ, q, F⟩, for hvilken der gælder:

• Q = Q₁ ∪ Q₂ (samtidig antager vi, at Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

Overgangsfunktionen δ opstiller vi efterhånden:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{hvis}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{hvis}& q\in F_1\wedge a\ne \epsilon \\ {\delta }_1(q,a)\cup \left\{p_0\right\}& \text{hvis}& q\in F_1\wedge a=\epsilon \\ {\delta }_2(q,a)& \text{hvis}& q\in Q_2\end{array}$$

Kilder

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools