FOR FREE YEAR SOLVED

Language in Automata, Union of two languages, Intersection of two languages, Complement of language, Reversal of language, Concatenation of two languages:  

Definition of Language in Automata:

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.

Language in Automata:

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 L1 = {aa.bb} or L2 = {aabb, bbaa, aba} (finite set of strings) L3 = an bn| n ≥ 0 (infinite set of strings) 

Operation of language:

Union of two languages :- Let language L1 = {01, 11, 101, 110} and L2 = {10, 11,110, 001} then

L3 = L1 ∪ L2 = { 01, 11, 101, 110} ∪ {10, 11, 110, 001} = {01, 11, 101, 110, 10, 001}

Intersection of two languages :- Let language L1 = {01, 11, 101, 110} and L2 = {10, 11,110, 001} then

L3 = L1 ∩ L2 = {01, 11, 101, 110} ∩ {10, 11, 110, 001} = {11, 110}

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

A complement of the language L¯ is just like a set where AC = U (Universal set) – A  

[here universal set is ∑*]

LC = L¯ = ∑*   - L, L ∪ LC = ∑*   = ∪ , L ∩ LC = Φ

Example:

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

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

A complement of this language  L¯= (set of all string not starting with a or not ending with b)

Reversal of Language: -  Reversal of the language is denoted by LR {ωR, ω∈ L}

Let L = {aa, ab, abb, aba,}  then LR = {aa, ba, bba, aba}

Concatenation of two languages :- L1.L2 = {xy : x ∈ L1, y ∈ L2}. Let  L1 = {a, ba}  and L2 = {b,aa}

 L1.L2 = {a, ba}{b,aa} = {ab, aaa, bab, baaa}

Power of Language L:- Ln = 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}

One interesting example on language operation:

Interesting example on language operation

Some important points of language:

Important points of language