Lecture No. 02
Dated: 25-10-2024
Kleene Star Closure
Given a \(\Sigma\), the kleene star closure denoted by \(\Sigma^*\) is a set1 of all possible strings2 which can be derived out of \(\Sigma\).
Example
\[\Sigma = \{0, 1\}\]
\[\Sigma^* = \{\Lambda, 0, 1, 00, 01, 10, 11, \ldots\}\]
Languages generated by kleene star closure are infinite, meaning they have infinite amount of words2 with infinite about of length.
Plus Operation +
It is same as kleene star closure but it does not generates \(\Lambda\).
Example
\[\Sigma = \{0, 1\}\]
\[\Sigma^+ = \{0, 1, 00, 01, 10, 11, \ldots\}\]
Recursive Definition
Following 3 steps are used to define a language recursively:
- Some basic words are specified in the
language. - Rules for constructing more words are defined in a
language. - Only the
strings2 generated by the above step is allowed in thelanguage.
Example
- \(x\) is an
integer. - If \(x\) is an
integerthen \(x + 1\) and \(x - 1\) are alsointegers. - Any other
string2 generated which does no followsstep 2is not allowed in thelanguage.