FOR FREE CONTENT

Subject Mock

A general definition of language must cover a variety of distinct categories: natural languages, programming languages, mathematical languages, etc. The notion of natural languages like English, Hindi, etc. is familiar to us. Informally, language can be defined as a system suitable for the expression of certain ideas, facts, or concepts, which includes a set of symbols and rules to manipulate these.

The languages we consider for our discussion is an abstraction of natural languages. That is, our focus here is on formal languages that need precise and formal definitions. Programming languages belong to this category. We start with some basic concepts and definitions required in this regard.

Definition:

A language is a set of strings over that alphabet ∑. Therefore, a language L is any subset of ∑* i.e. L ⊆ ∑*.

Example let ∑ = {a,b} so, Language L can be any finite and infinite subset of ∑*.

Like $L_{1}$ = {aa.bb} or $L_{2}$ = {aabb, bbaa, aba} (finite set of strings) $L_{3}$ = $a^{n} b^{n}$ | n ≥ 0 (infinite set of strings)

OPERATION OF LANGUAGE:

Union:- Let language $L_{1}$ = {01, 11, 101, 110} and $L_{2}$ = {10, 11,110, 001} then

$L_{3}$ = $L_{1}$ ∪ $L_{2}$ = { 01, 11, 101, 110} ∪ {10, 11, 110, 001} = {01, 11, 101, 110, 10, 001}

Intersection:- Let language $L_{1}$ = {01, 11, 101, 110} and $L_{2}$ = {10, 11,110, 001} then

$L_{3}$ = $L_{1}$ ∩ $L_{2}$ = {01, 11, 101, 110} ∩ {10, 11, 110, 001} = {11, 110}

Complement: - ∑ = {a,b} then ∑* = {λ, a, b, aa, ba, bb, …..} (set of all strings generated by a,b).

A complement of the language $\bar{L}$ is just like a set where $A^{C}$ = U (Universal set) – A

[here universal set is ∑*]

$L^{C} = \bar{L} = {\sum^{*}}_{}^{} - L, L \cup L^{C} = {\sum^{*}}_{}^{} = \cup, L \cap L^{C} = Φ$

Example:

Say one language set of all even string L = {| $ω$ | mod 2} then $L^{C}$ = {| $ω$ | mod 2 = 1}

Another example L= (set of all string starting with a and ending with b) then

A complement of this language $\bar{L}$ = (set of all string not starting with a or not ending with b)

Reversal of Language: - Reversal of the language is denoted by $L^{R} {ω^{R}, ω \in L}$

Let L = {aa, ab, abb, aba,} then $L^{R}$ = {aa, ba, bba, aba}

Concatenation:- $L_{1}$ . $L_{2}$ = { $x y : x \in L_{1}, y \in L_{2}$ }. Let $L_{1}$ = {a, ba} and $L_{2}$ = {b,aa}

$L_{1}$ . $L_{2}$ = {a, ba}{b,aa} = {ab, aaa, bab, baaa}

Power of Language L:- $L^{n}$ = L concatenated n times. Let L = {ab, ba}

Kleen's star operation:- Kleens’s star operation on language L is denoted by L*.

={x | x is the concatenation of zero or more strings from L}

Example: L = {a, b}

Same way

= {x | x is the concatenation of one or more strings from L}

Please Login to Bookmark