Lecture No. 04

Dated: 25-10-2024

Imagine we have \(\Sigma = \{a, b\}\) then a language \(L\) having even number of \(a\) and \(b\) can be defined as

\[(aa + bb + (ab + ba) (aa + bb)^*(ab + ba))^*\]

Note

1. \[r_1 = a^* + b^*\]
2. \[r_2 = (a + b)^*\]

The \(r_1\) does not generate any concatenation of \(a\) and \(b\) meanwhile \(r_2\) does.

Equivalent Regular Expressions

Two regular expressions¹ are called equivalent if both of them produce the same language.

Example

\[r_1 = (a + b)^*(aa + bb)\]

\[r_2 = (a + b)^*aa + (a + b)^*bb\]

Both define a language consisting of strings² ending with either \(aa\) or \(bb\).

Regular Languages

The language generated by any regular expression¹ is called regular language.

Note

If \(L_1\) and \(L_2\) are generated by \(r_1\) and \(r_2\) then following are true:

1. \(r_1 + r_2 \to L_1 + L_2\) or \(L_1 \cup L_2\)
2. \(r_1r_2 \to L_1L_2\) such that each string² of \(L_1\) is prefixed with every string² of \(L_2\)
3. \(r_1^* \to L_1^*\) such that the strings² are concatenated by the strings² of \(L\), including \(\Lambda\)

All finite languages are regular.

Finite Automaton

Imagine a game board with 64 boxes.
Then there are 64 or less pieces of paper which are colored either white or black.
The number of arrangements in which these pieces of paper can be placed in the boxes is finite.
To start the game, one of the arrangement needs to be initialized.
There is a pair of dices which can generate numbers from 2 to 12.
Each number is associated with a possible arrangement.
One or more arrangements can be considered as winning.
Winning of the game depends on the sequence in which the numbers are generated.
This structure of the game can be considered to be a finite automaton.

Another Definition

It is a collection of following:

• Finite number of states, one being initial and possibly other being a final one.
• Finite set³ of input letters from which input strings are formed.
• Finite set³ of transitions of states.

Example

\[\Sigma = \{a, b\}\]

States

\(x\), \(y\), \(z\) where \(x\) is initial state and \(z\) is final state.

Transitions

• At state \(x\) reading a, go to state \(z\).
• At state \(x\) reading b, go to state \(y\).
• At state \(y\) reading a, b, go to state \(y\).
• At state \(z\) reading a, b, go to state \(z\).

Transition Table

Old States	New States
	Reading \(a\)	Reading \(b\)
\(x^-\)	\(z\)	\(y\)
\(y\)	\(y\)	\(y\)
\(z^+\)	\(z\)	\(z\)

Transition Diagram

This language can be represented as \(a(a + b)^*\).

References

---

1. Read more about regular expressions. ↩↩

2. Read more about strings. ↩↩↩↩↩

3. Read more about sets. ↩↩