Skip to content

Languages ​

Alphabet, Word ​

An alphabet V is a finite non-empty set of symbols or letters.

A finite sequence of symbols or letters (string) is also called a word over V.

The set of all words over V (including the empty word ε) is denoted by V∗.

The set of all non-empty words over V is denoted by V+.

Length of a word ​

Let u∈V∗ be a word.

The length of u is the number of symbols in u and is denoted by |u|.

Note that |ε|=0.

Concatenation of words ​

Let u,v∈V∗ be words.

The concatenation of u and v is the word uv.

V∗ is a monoid with respect to concatenation, meaning that concatenation is associative and has an identity element, namely, εu=u=uε for all u∈V∗.

Subword ​

Two words over V are equal if they have the same length and the same symbols at each position.

A word u∈V∗ is a subword or part of a word v∈V∗ if there exist words x,y∈V∗ such that v=xuy.

u is a proper subword of v if u≠v, so at least one of x and y is non-empty.

Prefix, Suffix ​

A word u∈V∗ is a prefix of a word v∈V∗ if there exists a word x∈V∗ such that v=ux.

A word u∈V∗ is a suffix of a word v∈V∗ if there exists a word x∈V∗ such that v=xu.

Reversal (mirror image) ​

The reversal or mirror image of a word u∈V∗ is the word uR obtained by writing the symbols of u in reverse order.

For u=a1a2…an, we have uR=an…a2a1, where 1≤i≤n.

Power of a word ​

Let i∈N+ and u∈V∗ be a word.

The power of u or the i-th time concatenation of u is the word ui, meaning that i copies of u are concatenated.

By convention, u0=ε.

Language ​

For an alphabet V, a subset L⊆V∗ is called a language over V.

The empty language is denoted by L=∅.

A language is finite if it contains a finite number of words, and infinite otherwise.

Occurrence of symbols ​

Notation Na(u) denotes the number of occurrences of symbol a in word u.

Operations on languages ​

Let L1,L2⊆V∗ be languages.

Union ​

The union of L1 and L2 is the language L1∪L2={u∣u∈L1∨u∈L2}

Meaning that L1∪L2 contains words that are in either L1 or L2.

Intersection ​

The intersection of L1 and L2 is the language L1∩L2={u∣u∈L1∧u∈L2}

Meaning that L1∩L2 contains words that are in both L1 and L2.

Difference ​

The difference of L1 and L2 is the language L1∖L2={u∣u∈L1∧u∉L2}

Can also be denoted by L1−L2.

Meaning that L1∖L2 contains words that are in L1 but not in L2.

Complement ​

The complement of L1 is the language L1―=V∗∖L1={u∣u∈V∗∧u∉L1}

Meaning that L1― contains all words over V that are not in L1.

Reversal ​

The reversal of L1 is the language L1R={uR∣u∈L1}

Meaning that L1R contains the reversal of all words in L1.

Concatenation ​

The concatenation of L1 and L2 is the language L1L2={uv∣u∈L1∧v∈L2}

Meaning that L1L2 contains words that represent all possible concatenations of words from L1 and L2.

Power ​

The power of L1 is the language L1i={u1u2…ui∣u1,u2,…,ui∈L1}

Meaning that L1i contains words that represent all possible concatenations of i words from L1.

Note that L10={ε} and L1i=L1L1i−1 for i≥1.

Closure ​

The closure of L1 is the language L1∗=⋃i=0∞L1i

Meaning that L1∗ contains words that represent all possible concatenations of any number of words from L1.

Positive closure ​

The positive closure of L1 is the language L1+=⋃i=1∞L1i

Meaning that L1+ contains words that represent all possible concatenations of at least one word from L1.

Note that L1+=L1∗ if ε∈L1 and L1+=L1∗−{ε} if ε∉L1.

Prefix ​

The prefix of L1 is the language Pre(L1)={u∣u∈V∗∧∃v∈L1:v=ux}

Meaning that Pre(L1) contains all prefixes of words in L1.

Suffix ​

The suffix of L1 is the language Suf(L1)={u∣u∈V∗∧∃v∈L1:v=xu}

Meaning that Suf(L1) contains all suffixes of words in L1.

Homomorphism ​

A homomorphism is a function h:V1∗→V2∗ that maps symbols of alphabet V1 to words over alphabet V2, given that h(ε)=ε and h(uv)=h(u)h(v) for all u,v∈V1∗.

Image of a language ​

The image of a language L1 under homomorphism h is the language h(L1)={h(u)∣u∈L1}

Meaning that h(L1) contains all words that are obtained by applying h to words in L1.

Example 1 ​

Let u=ababb and v=cbb.

Find uR, uv, vu, list prefixes and suffixes of u, and find u0, u1, u2, u3.

Solution ​

uR=bbabauv=ababbcbbvu=cbbababb

Prefixes of u:

  • ε
  • a
  • ab
  • aba
  • abab
  • ababb

Suffixes of u:

  • ε
  • b
  • bb
  • abb
  • babb
  • ababb
u0=εu1=ababbu2=ababbababbu3=ababbababbababb

Example 2 ​

Let V={a,b} and L1={ab,bb}, L2={ε,a,bba}.

Find L1L2.

Solution ​

L1L2={abε,bbε,aba,bba,abbba,bbbba}={ab,bb,aba,bba,abbba,bbbba}

Example 3 ​

Let L={a,bb}.

Find L0, L1, L2, L3, L∗, L+.

Solution ​

L0={ε}L1={a,bb}L2={aa,abb,bba,bbbb}L3={aaa,aabb,abba,abbbb,bbaa,bbabb,bbbba,bbbbbb}L∗={ε,a,bb,aa,abb,bba,bbbb,aaa,aabb,abba,abbbb,bbaa,bbabb,bbbba,bbbbbb,…}L+={a,bb,aa,abb,bba,bbbb,aaa,aabb,abba,abbbb,bbaa,bbabb,bbbba,bbbbbb,…}

Example 4 ​

Let V={a,b} and L={ba2n+1∣n∈N}.

Find LR.

Solution ​

LR={(ba2n+1)R∣n∈N}={a2n+1b∣n∈N}

Example 5 ​

Let L={cab,cbab}.

Find Pre(L) and Suf(L).

Solution ​

Pre(L)={ε,c,ca,cab,crepeat,cb,cba,cbab}={ε,c,ca,cab,cb,cba,cbab}Suf(L)={ε,b,ab,cab,brepeat,abrepeat,bab,cbab}={ε,b,ab,cab,bab,cbab}

Example 6 ​

Let V1={a,b}, V2={b,c}, L={anban∣n∈N}.

h:V1∗→V2∗ be a homomorphism such that h(a)=cc and h(b)=cbb.

Find h(L).

Solution ​

h(L)={h(anban)∣n∈N}=={h(an)h(b)h(an)∣n∈N}=={(cc)ncbb(cc)n∣n∈N}=={c2n+1b2c2n∣n∈N}

Example 7 ​

Let V={a,b},

L1={a2n+1b∣n≥0}L2={anbn∣n≥0}L3={a2n∣n≥0}

Find

  • L1∩L2
  • L2∩L3
  • L1∩L3
  • L1∪L2
  • L1L2
  • L12
  • L1∗
  • Pre(L1)
  • Suf(L1)
  • L3―

Solution ​

  • L1∩L2
L1∩L2={a2n+1b∣n≥0}∩{anbn∣n≥0}={ab}
  • L2∩L3
L2∩L3={anbn∣n≥0}∩{a2n∣n≥0}={ε}
  • L1∩L3
L1∩L3={a2n+1b∣n≥0}∩{a2n∣n≥0}=∅
  • L1∪L2
L1∪L2={a2n+1b∣n≥0}∪{anbn∣n≥0}
  • L1L2
L1L2={a2n+1banbn∣n≥0}
  • L12
L12={a2n+1ba2m+1b∣n,m≥0}
  • L1∗
L1∗={a2n+1b∣n≥0}∗={ε,ab,abab,…,a3b,a3ba3b,…}
  • Pre(L1)
Pre(L1)={ε,a,a2,a3,…,a2n+1,a2n+1b∣n≥0}=={an∣n≥0}∪{a2n+1b∣n≥0}
  • Suf(L1)
Suf(L1)={ε,b,ab,a2b,…,a2n+1b∣n≥0}=={ε}∪{anb∣n≥0}

Example 8 ​

Let L={(ab)nb2n+1∣n∈N}, h(a)=xyy, h(b)=yy.

Find h(L).

Solution ​

h(L)={h((ab)nb2n+1)∣n∈N}=={h(ab)nh(b)2n+1∣n∈N}=={(xyyyy)n(yy)2n+1∣n∈N}=={xny4ny4n+2∣n∈N}=={xny8n+2∣n∈N}