Konkateneringen av to språk $L$ og $M$ er definert som $LM = \set{st \mid s \in L \text{ og } t \in M}$. Det betyr at hver streng i $L$ skal konkateneres med hver streng i $M$, og strengene fra $L$ skal forekomme først.
Kapitteltest – Kapittel 23
Oppgave
Hvilke av disse språkene er regulære?
Dette er ikke et regulært språk, siden det ikke kan representeres med kun operasjonene konkatenering, union og tillukningen av andre språk. Språket kan representeres som $\set{\str{a}^n \str{b}^n | n \in \mathbb{N} }$. Det at det skal være samme antall $\str{a}$-er og $\str{b}$-er, gjør at det ikke er et regulært språk.
Dette er et regulært språk, siden det kan representeres med det regulære uttrykket $\str{(b|} \tomstreng \str{)a}\xx$.
Dette er et regulært språk, siden det kan representeres med det regulære uttrykket $\str{bc(bc)}\xx\str{|}\str{bb(bb)}\xx$
Oppgave
La $L = \set{\str{a}, \str{bb}, \str{ca}}$ og $M = \set{\str{bb}, \str{ac}}$ være to språk. Hva blir konkateneringen $LM$ av disse språkene?