Department of CE

TAFL : Theory of Automata and Formal

Languages Unit no : 1
Preliminaries
(01CE0504)

Preliminaries

Prof. Dhara Sapara

UNIT 1 (Part II)
Department of CE

Outline :
Inverse Function Unit no : 1
Introduction to
Relations Compiler
Mathematical Proof Techniques (01CE0504)
Languages

Prof. Dhara Sapara

Inverse Function
   An inverse function is a function that "reverses"
another function: if the function f applied to an
input x gives a result of y, then applying its inverse
function g to y gives the result x, and vice versa,
i.e., f(x) = y if and only if g(y) = x.
 For a function to be an invertible, it must be an
Inverse injection and a surjection.
Function  Example:

1 A A 1

2 B B 2

3 C C 3
f f -1
 Steps required to find the inverse function:
Example  Step 1: Replace f(x) with y
(Inverse  Step 2: Swap x and y
Function)  Step 3: Isolate/Solve for y
 Step 4: Replace y with f -1(x)
 Find the inverse function of f(x) = (x – 3)/2
Example  y = (x – 3)/2
(Inverse  x = (y – 3)/2
Function)  2x + 3 = y
 2x + 3 = f -1(x)
 Find the inverse function of f(x) = (3x2 – 7)/4 +5
 y = (3x2 – 7)/4 +5

 x = (3y2 – 7)/4 +5
Example
(Inverse  (x – 5) * 4 = 3y2 – 7
Function)  4x – 13 = 3y2
 (4x – 13)/3 = y2
 sqrt[(4x – 13)/3] = y
 sqrt[(4x – 13)/3] = f -1(x)
 To verify that f −1 is really the inverse of f, we should
show that the composition of f and f −1 doesn't do
anything to the input.
In previous example, f(x) = (3x2 – 7)/4 + 5 and f -1(x) =
sqrt[(4x – 13)/3]
Check (f ∘ f -1)(x) Check(f -1 ∘ f )(x)
Inverse = f (f -1(x)) = f -1 (f(x))
Function = f(sqrt[(4x – 13)/3]) = f -1 [(3x2 – 7)/4 + 5]
= {3[(4x – 13)/ 3] – 7 }/4 + 5 = sqrt{[4((3x2 – 7)/4 + 5) – 13]/3}
= (4x – 20)/4 + 5 = sqrt{[(3x2 – 7) + 20 – 13]/3}
= x – 5 + 5 = sqrt{[3x2]/3}
=x = sqrt{x2}
=x
 Let f : R → R be defined by f(x) = x2. Does this
function posses an inverse function?
 For any real number x, f(x) and f(-x) results in same
value as f(x) = f(-x) = x2
 Moreover, if x ≠ 0, then x and –x are two different
Example numbers, and f maps these two distinct numbers to
the same output value.
 If output of f(x) was given as y = 4, there’s no way to
know if x = 2 or x = -2 was the input function.
 Hence, function f doesn’t have inverse function
possible.
 Let f : R+ → R be defined by f(x) = x2. Does this
function posses an inverse function? If so, find f -1.
 In this case, we have restricted the domain to the
non-negative real numbers.
Example  Hence, every distinct input value x ≥ 0 will yield a
distinct output value x2. For this function, we can find
its inverse.
 y = f(x) = x2.
 Hence, x = sqrt(y) and f -1(y) = sqrt(y).
Relations
   Relations may exist between objects of the same set
or between objects of two or more sets.
 A binary relation R from set x to y is written as xRy or
R(x, y), which is a subset of the Cartesian product x x
y.
 Domain of R is the set {x | (x, y) ∈ R for some y in B}
Relations  Range of R, is the set {y | (x, y) ∈ R for some x in A}
 Example:
A= {1, 2, 3}
A x A = {(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2)
(3,3)}
“>” relation on A x A results in, {(2,1) (3,1) (3,2)}
  We say ∼ is an equivalence relation on a set A, if it
satisfies the following three properties:
Equivalence  a) reflexivity: for all a ∈ A, a∼a.
Relation  b) symmetry: for all a,b ∈ A, if a∼b then b∼a.
 c) transitivity: for all a,b,c ∈ A, if a∼b and b∼c then
a∼c
  A = {1, 2, 3}
 R = {(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2)
(3,3)}
Example  {(1, 1) (2, 2) (3, 3)} is reflexive.
(Relation)  {(2, 3) (3, 2) (1, 1)} is symmetric.
 {(2, 3) (3, 2) (1, 1) (2, 2)} is symmetric and transitive.
 {(1,2) (2,3) (1, 3)} is transitive.
 Exercise:
1. A = {a, b, c}, R = {(a, b) (a, a) (b, a) (b, b) (c, b) (c, c)}
does this relation is equivalent relation?
Example 2. Let A = {1, 2, 3, 4, 5}, R = {(a, b) | (a + b) is even}. R
(Relation) is relation on set A. Show that R is an equivalence
relation.
3. Let A = Z and let R = {(a, b) ∈ A x A : a ≡ b(mod 2)}.
Show that R is an equivalence relation.
 R = {(a, b) | (a + b) is even}
 Reflexive:
 Odd + odd = even and even + even = even.
 Here, same term is added, which results in even value.
 Symmetric:

Exercise 2  If (a + b) is even, then (b + a) is also even.

 Transitive:
(Answer)  a + b and b + c are even.
 ⇒ a + b = 2x, b + c = 2y
 ⇒ a + 2b + c = 2(x + y)
 ⇒ a + c = 2(x + y) – 2b
 Moreover, even – even = even only.
 This proves, relation is equivalent.
 R = {(a, b) ∈ A x A : a ≡ b(mod 2)}
 Reflexive:
 a ≡ a(mod 2) means, a – a is divisible by m.
 And 0 is divisible by all the integers, this proves reflexive.
 Symmetric:
Exercise 3  |a – b| is divisible by 2, then |b – a| is also divisible by 2.

(Answer)  Transitive:
 a ≡ b(mod 2) ⇒ a – b = 2Q1
 b ≡ c(mod 2) ⇒ b – c = 2Q2
 a – b + b – c = 2(Q1 + Q2)
 ⇒ a – c = 2(Q1 + Q2)
 Hence, a – c is also divisible by 2. This proves, transitivity.
Proof
  A proof is a statement is essentially just a convincing
argument that the statement is true.
 Steps in the proof are there to derive some
statements from:
 Assumptions or hypothesis
 Statements that have already been derived
Proof  Other generally accepted facts
 Methods to establish a proof, some of them are:
 Direct proof
 Proof by contradiction
 Proof by contrapositive
 Proof by mathematical induction
  The simplest (from a logic perspective) style of proof
is a direct proof.
 Often all that is required to prove something is a
systematic explanation of what everything means.
Direct Proof  Direct proofs are especially useful when proving
implications.
 The general format to prove P→Q is this:
 Assume P. Explain, explain, …, explain. Therefore Q.
 Prove: For all integers n, if n is even, then n2 is
even.
Example Solution:
 Let n be an arbitrary integer. Suppose n is even.
(Direct
 Then n=2k for some integer k. 
Proof)
 Now n2=(2k)2=4k2=2(2k2).  
 Since 2k2 is an integer, n2 is even.
 Prove: For all integers a, b, and c, if a|b and b|c then a|
c. Here x|y, read “x divides y” means that y is a multiple
of x (so x will divide into y without remainder).
Solution:
 Let a, b, and c be integers.
Example
 Assume that a|b and b|c. 
(Direct
 In other words, b is a multiple of a and c is a multiple
Proof) of b. So there are integers k and j such that b=ka and c=jb. 
 Combining these (through substitution) we get that c=jka. 
 But jk is an integer, so this says that c is a multiple
of a. Therefore a|c.
  It is known that, an implication P→Q is logically
equivalent to its contrapositive ¬Q→¬P. 
 There are plenty of examples of statements which are
Proof by hard to prove directly, but whose contrapositive can
Contrapositiv easily be proved directly.
 This is all that proof by contrapositive does. It gives
e a direct proof of the contrapositive of the implication.
 This is enough because the contrapositive is logically
equivalent to the original implication.
 Prove: For all integers a and b, if a + b is odd, then a
is odd or b is odd.
Solution:
Example  (Let a and b be integers, assume that a and b are even.
(Proof by EXPLAIN. Therefore a + b is even.)
 Let a and b be integers. Assume that a and b are even.
Contrapositiv
 Then a =2k and b = 2l for some integers l and k.
e)
 Now, a + b = 2k + 2l = 2(k + l).
 Since k+ l is an integer, we see that a+ b is even, this
completes the proof.
 Prove: For every prime number, if p ≠ 2, then p is
odd.
Solution:
Example  Let p be an arbitrary prime number.
(Proof by  Assume p is not odd.
Contrapositiv  So p is divisible by 2.
e)  Since p is prime. It must have exactly two divisors,
and it has 2 as a divisor, so p must be divisible by 1
and 2.
 Therefore p = 2. This completes the proof.
  Some statements cannot be rephrased as
implications. It might be the case where, it is hard to
decide from where to start.
Proof by  In proof by contradiction it process works as below:
Contradictio  If we can prove that ¬P leads to a contradiction, then
the only conclusion is that ¬P is false, so P is true.
n  That's what we wanted to prove.
 In other words, if it is impossible for P to be
false, P must be true.
 Prove: Suppose a ∈ Z. If a2 is even, then a is even.
Solution:
 For the sake of contradiction suppose a2 is even and a
is not even.
Example  Then a2 is even, and a is odd.
(Proof by  Since a is odd, there is an integer c for which a = 2c +1.
Contradictio  Then a2 = (2c +1)2 = 4c2 +4c +1 = 2(2c2 +2c)+1, so a2 is
n) odd.
 Thus a2 is even and a2 is not even, a contradiction.
 (And since we have arrived at a contradiction, our
original supposition that a2 is even and a is odd could
not be true.)
 Prove: There are no integers x and y such that x2=4y+2.
Solution: 
 We proceed by contradiction.
 So suppose there are integers x and y such that x2 = 4y+2 =
Example 2(2y+1). 
(Proof by  So x2 is even. This implies that x is even.
Contradictio  So x = 2k for some integer k. 
n)  Then x2 = 4k2.
 This in turn gives 2k2 = (2y+1).
 But 2k2 is even, and 2y+1 is odd, so these cannot be equal.
 Thus we have a contradiction, so there must not be any
integers x and y such that x2=4y+2.
 Prove: The Pigeonhole Principle: If more
than n pigeons fly into n pigeon holes, then at least
one pigeon hole will contain at least two pigeons.
Solution:
Example
 Suppose, contrary to stipulation, that each of the
(Proof by pigeon holes contain at most one pigeon.
Contradictio  Then at most, there will be n pigeons.
n)  But we assumed that there are more than n pigeons,
so this is impossible.
 Thus there must be a pigeonhole with more than one
pigeon.
  Prove: √2 is irrational
(Definition: A real number is rational if there are two
integers m and n so that x= m/n)
Proof:
Example  For the sake of contradiction, assume √2 is rational.
(Proof by  Hence, some integers m’ and n’ are there, such that
Contradictio √2 = m’/n’
n)  By dividing m’ and n’ by all the factors that are
common in both, we obtain √2 = m/n, for some
integers m and n, which has no common factors.
 Since, √2 = m/n, m =n √2. squaring both sides will
result in, m2 = 2n2, hence, m2 is even.
  If a and b are odd, then ab is odd. Since a conditional
statement is logically equivalent to its contra positive,
we may conclude that for any a and b, if ab is not odd,
then either a is not odd or b is not odd.
 However, an integer is not odd if and only if it is even,
Continued…. and so for any a and b, if ab is even, then a or b is
even.
 If we apply this when a = b = m, we conclude that
since m2 is even, m must be even.
 This means that for some k, m = 2k. Therefore, (2k)2
= 2n2.
  Simplifying and cancelling 2 from both sides, we
obtain 2k2 = n2. Therefore n2 is even and therefore n =
2j for some j.
 We have shown that m and n are both divisible by 2.
Continued…. This contradicts the previous statement that m and n
have no common factor.
 The assumption that √2 is rational therefore leads to
a contradiction, and the conclusion is that √2 is
irrational.
 Principle of
Mathematical Induction
  Mathematical Induction is a technique of proving a
statement, theorem or formula, which is thought to be true.
 Consider a statement P(n), where n is a natural number. Then
to determine the validity of P(n) for every n, use the following
principle:
 Step 1:  Check whether the given statement is true for n = n0.
Mathematical (n0 = base case)
 Step 2: Assume that given statement P(n) is also true for n = k,
Induction where k is any positive integer. (Induction Hypothesis)
 Step 3:  Prove that the result is true for P(k+1) for any positive
integer k. (Proof of Induction)
 If the above-mentioned conditions are satisfied, then it can be
concluded that P(n) is true for all n natural numbers.
 Prove that the sum of all natural numbers is equal to
n(n + 1) / 2
 Basic step:
 We must show that it is true for P(1).
 P(1) = 1 for LHS
Example  P(1) = 1(1+1)/2 for RHS, and this proves true.

(Mathematic  Induction Hypothesis:

 For k ≥ 1, 1 + 2 + 3 +…. + k = k(k+1)/2
al Induction)  Proof of Induction:
 P(k+1) = 1 + 2 + 3 +…. + k + (k+1)
= k(k+1)/2 + (k+1) (by hypothesis)
= (k + 1)(k/2 + 1)
= (k + 1)(k + 2)/2
= (k + 1)((k + 1) + 1)/2 (Proved)
Using the principle of mathematical induction, prove that,
1 x 2 + 3 x 4 + 5 x 6 + …. + (2n - 1) x 2n = {n(n+1)(4n−1)}/3 for all n ∈ N.
Basic step:
We must show that it is true for P(1).
P(1) = (2x1 – 1) x 2(1) = 2 for LHS
P(1) = 1(1+1)(4x1 – 1)/3 = 2 for RHS, and this proves true.
Induction Hypothesis:
1 x 2 + 3 x 4 + 5 x 6 + …. + (2k - 1) x 2k = {k(k+1)(4k−1)}/3 (We assume P(k) is
true)
Proof of Induction:
P(k+1) = 1 x 2 + 3 x 4 + 5 x 6 + …. + (2k - 1) x 2k + (2(k + 1) - 1) x 2(k + 1)
= {k(k+1)(4k−1)}/3 + (2(k + 1) - 1) x 2(k + 1) (by hypothesis)
= {(k+1)/3}(4k2 - k + 12 k + 6)
= {(k+1)(4k2+8k+3k+6)}/3
= {(k+1)(k+2)(4k+3)}/3
= {(k+1)((k+1)+1)(4(k+1)−1)}/3 (Proved)
Using the principle of mathematical induction, prove that,
1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ..... + n(n + 1) = (1/3){n(n + 1)(n + 2)} for all n ∈ N.
Basic step:
We must show that it is true for P(1).
P(1) = 1(1 + 1) = 2 for LHS
P(1) = (1/3){1(1+1)(1 + 2)} = 2 for RHS, and this proves true.
Induction Hypothesis:
1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ..... + k(k + 1) = (1/3){k(k + 1)(k + 2)} (We assume P(k) is true)
Proof of Induction:
P(k+1) = 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 +...+ k(k + 1) + (k + 1)(k + 2)
= (1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ....... + k(k + 1)) + (k + 1)(k + 2)
= (1/3) {k(k + 1)(k + 2)} + (k + 1)(k + 2) (by hypothesis)
= (1/3){(k + 1)(k + 2)(k + 3)}

⇒ P(k + 1): 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 +......+ (k + 1)(k + 2)

= (1/3){k + 1 )(k + 2)(k +3)} (proved)
Using the principle of mathematical induction, prove that,
2 + 6 + 10 + ….. + (4n - 2) = 2n2, for all positive integers.
Basic step:
We must show that it is true for P(1).
P(1) = (4 x 1 – 2) = 2 for LHS
P(1) = 2 x 12 = 2 for RHS, and this proves true.
Induction Hypothesis:
2 + 6 + 10 + ….. + (4k - 2) = 2k2 (We assume P(k) is true)
Proof of Induction:
P(k+1) =2 + 6 + 10 + ….. + (4k - 2) + (4(k + 1) - 2)
= 2k2 + (4k + 4 - 2) (by hypothesis)
= 2k2 + 4k + 2
= (k+1)2 (proved)
Using the principle of mathematical induction, prove that,
7 + 13 + 19 +……+ (6n + 1) = n(3n + 4), for n >= 1
Basic step:
We must show that it is true for P(1).
P(1) = 6(1) + 1 = 7 for LHS
P(1) = 1(3x1 + 4) = 7 for RHS, and this proves true.
Induction Hypothesis:
k >= 1, 7 + 13 + 19 +......+ (6k + 1) = k(3k + 4) (We assume P(k) is true)
Proof of Induction:
P(k+1) = 7 + 13 + 19 +......+ (6k + 1) + (6(k + 1) + 1)
= k(3k + 4) + (6(k + 1) + 1) (by hypothesis)
= 3k2 + 4k + 6k + 7
= 3k2 + 10k + 7
= 3k2 + 7k + 3k + 7
= k(3k + 7) + 3k + 7
= (k + 1)(3k + 7)
= (k + 1)(3k + 3 + 4)
= (k + 1)(3(k + 1) + 4) (proved)
Using the principle of mathematical induction, prove that,
n(n2 + 5) is divisible by 6.
Basic step:
We must show that it is true for P(1).
P(1) = 1(12 + 5) = 6, here 6 is divisible by 6. This proves true for basic step.
Induction Hypothesis:
For k >= 1, P(k) = k(k2 + 5) is divisible by 6. (We assume P(k) is true)
Proof of Induction:
P(k+1) = (k+1)[(k+1)2 + 5]
= (k+1)(k2+2k+1+5)
= (k+1)(k2+2k+6)
= k3+2k2+6k+k2+2k+6
= k3+3k2+8k+6
= k3+3k2+5k+3k+6
= k(k2+5)+3k(k+1)+6
Here, k(k2+5) is divisible by 6. (By induction hypothesis)
In second term k and k+1 are consecutive. So, one number is even and another is odd. So, even
number is multiple of 2 always. Moreover, here 3 is also present. So, second term is having (2*3),
which is also divisible by 6.
Last term is 6, which is obviously divisible by 6. Hence, proved.
Using the principle of mathematical induction, prove that, 2n >= n2, for n >= 4
First to solve this prove, 2n >= 2n + 1, for n >= 4
Basic step:
We must show that it is true for P(1).
P(1) = 24 = 16 for LHS
P(1) = 2(4) + 1 = 9 for RHS, and 16 >= 9, hence, this proves true.
Induction Hypothesis:
For k >= 4, 2k >= 2k + 1 (We assume P(k) is true)
Proof of Induction:
P(k+1) = 2k+1 >= 2k + 3
⇒ 2k+1 – (2k + 3) = 2(2k) – 2k – 3
⇒ 2k+1 – (2k + 3) >= 2(2k + 1) -2k -3 (By induction hypothesis)
>= 4k + 2 – 2k – 3
⇒ 2k+1 – (2k + 3) >= 2k – 1 (but k >= 4)
⇒ 2k+1 – (2k + 3) >= 8 – 1
⇒ 2k+1 – (2k + 3) >= 7 >= 0
⇒ 2k+1 >= (2k + 3)
Hence, statement is true for n = k + 1. By P. M. I. 2n > 2n + 1, for n >= 4
Using the principle of mathematical induction, prove that, 2n >= n2, for n >= 4
Continued…
Now, solve for 2n >= n2, for n >= 4
Basic step:
We must show that it is true for P(1).
P(1) = 24 = 16 for LHS
P(1) = 42 = 16 for RHS, and 16 >= 16 , hence, this proves true.
Induction Hypothesis:
For k >= 4, 2k >= k2 (We assume P(k) is true)
Proof of Induction:
P(k+1) = 2k+1 >= (k + 1)2
⇒ 2k+1 – (k + 1)2 = 2(2k) – (k2 + 2k + 1)
⇒ 2k+1 – (k + 1)2 = 2k + 2k – (k2 + 2k + 1)
⇒ 2k+1 – (k + 1)2 >= 2k + k2 – (k2 + 2k + 1) (By induction hypothesis)
>= 2k – (2k + 1) (But 2k >= 2k + 1)
⇒ 2k+1 – (k + 1)2 >= 0
⇒ 2k+1 >= (k + 1)2
Hence, statement is true for n = k + 1. By P. M. I. 2n >= n2, for n >= 4
 Strong
Mathematical
Induction
  Suppose P(n) is a statement involving an integer n.
Strong  Then to prove that P(n) is true for every n >= n0, it is
Principle of sufficient to show these two things:
Mathematica  P(n0) is true.
 For any k >= n0, if P(n) Is true for every n satisfying n0
l Induction <= n <= k, then P(k + 1) is true.
Let an be the sequence defined by a1 = 1, a2 = 8, and an = an−1 + 2an−2 for n ≥ 3. Prove that an = 3 ·
2n−1 + 2(−1)n for all n ∈ N.
Proof:
We will prove by strong induction that, for all n ∈ N, an = 3 · 2n−1 + 2(−1)n . (1)
Base case:
When n = 1, LHS = a1 = 1, and RHS = 3 · 20 + 2 · (−1)1 = 1, so both sides are equal and (1) is true for n
= 1.
When n = 2, LHS = a2 = 8 and RHS = 3 · 21 + 2 · (−1)2 = 8, so (1) holds in this case as well.
Induction step:
Let k ∈ N with k ≥ 2 be given and suppose (1) is true for n = 1, 2, . . . , k.
Then ak+1 = ak + 2ak−1 (by recurrence for an)
= 3 · 2k−1 + 2 · (−1)k + 2 (3 · 2k−2 + 2 · (−1)k−1) (by (1) for n = k and n = k − 1)
= 3 · (2k−1 + 2k−1) + 2 ((−1)k + 2(−1)k−1) (by algebra)
= 3 · 2k + 2(−1)k+1 (more algebra)
Thus, (1) holds for n = k + 1, and the proof of the induction step is complete.
Conclusion: By the strong induction principle, it follows that (1) is true for all n ∈ N.
Any integer n ≥ 2 is either a prime or can be represented as a product of (not
necessarily distinct) primes, i.e., in the form n = p1p2 . . . pr, where the pi are primes.

Proof:
We will prove by strong induction that the following statement holds for all integers n ≥ 2.
(P(n)) n can be represented as a product of one or more primes.

Base case:
The integer n = 2 is a prime since it cannot be written as a product ab, with integers a, b ≥ 2,
so P(n) holds for n = 2.

Induction step:
• Let k ≥ 2 be given and suppose P(n) is true for all integers 2 ≤ n ≤ k, i.e., suppose that all
such n can be represented as a product of one or more primes.
• We seek to show that k + 1 also has a representation of this form.
• If k + 1 itself is prime, then P(n) holds for n = k + 1, and we are done.
• Now consider the case when k + 1 is composite.
Continued…
• By definition, this means that k + 1 can be written in the form k + 1 = ab, where a and b
are integers satisfying 2 ≤ a, b < k + 1, i.e., 2 ≤ a, b ≤ k.
• Since 2 ≤ a, b ≤ k, the induction hypothesis can be applied to a and b and shows that a
and b can be represented as products of one or more primes.
• Multiplying these two representations gives a representation of k + 1 as a product of
primes.
• Hence k + 1 has a representation of the desired form, so P(n) holds for n = k + 1, and
the induction step is complete.
Conclusion: By the strong induction principle, it follows that P(n) is true for all n ≥ 2, i.e.,
every integer n ≥ 2 is either a prime or can be represented as a product of primes
Languages
 An alphabet is a finite set of symbols. (Σ)
 Example:
Alphabets in C lang. or any programming lang.

 Σ = {0, 1} Binary Alphabet

Alphabet  Σ = {false, true} Boolean Alphabet
 Σ = {0, 1,… , 9} Decimal Alphabet
 Σ = {a, b}
 (To form sentences, we have words and in TAFL they are known
as “string”)
A string over an alphabet is a finite sequence of symbols drawn
from that alphabet.
 0 length string ε (epsilon) or ^ Σ0 = {0, 1}0
(null string / empty string / void string)

String
 1 length string 0 or 1 Σ1 = {0, 1}1

 2 length string 00, 01, 10, 11 Σ2 = {0, 1}2

Σ2 = Σ1 Σ1 = {0, 1}1{0, 1}1 (Concatenation)

All these are strings, they are not sets. (Set means written in {})
 A language is any countable set of strings over some fixed
alphabet.
Example: Σ = {0, 1}
 L = {} Empty Lang.
(Number of strings in Empty lang. = 0)

 L = {ε} (Number of strings in lang. = 1)

Language  L = {0}
 L = {ε, 00}
 L = {1}
 L = {0, 1}
 L = {00, 01, 100, 111}
 L = {0, 00, 000,…..} Infinite Lang.
  Σ is a particular alphabet.
 A set of all strings all of which are chosen from some Σ*, is
called a language.
 If Σ is an alphabet and L ⊆ Σ*, then L is said to be language
over alphabet Σ.
Language comprises of:
 Set of characters (Σ)
Language  Set of strings defined from set of characters (Σ*)
 Language L defined from Σ*, and L ⊆ Σ* because Σ* contains
many string which may not satisfy the rule of language.
Example:
 For Σ = {0, 1}
 Σ* = {^, 0, 1, 00, 01, 10, 11, 000, 010,……}
 Possible operations over any language are:
Operations  Union
over  Concatenation
Language  Kleene Closure (*)
 Positive Closure (+)
 If L1, L2 ⊆ Σ* then union is defined as:
 L1 | L2 = {x | x ∈ L1 or x ∈ L2}

Example:
Union  L1 = {ab, aaa} and L2 = {bba, aba}
Operation Ans: L1 | L2 = {ab, aaa, bba, aba}

 L1 = {bab, aabb, babaa} and L2 = {a, bb, ab}

Ans: L1 | L2 = {bab, aabb, babaa, a, bb, ab}
 If L1, L2 ⊆ Σ* then concatenation is defined as:
 L1L2 = {xy | x ∈ L1 and y ∈ L2}

Example:
Concatenatio  L1 = {ab, aaa} and L2 = {bba, aba}
n Operation Ans: L1 | L2 = {abbba, aaabba, aaaaba, ababa}

 L1 = {bab, aabb, babaa} and L2 = {a, bb, ab}

Ans: L1 | L2 = {baba, aabba, babaaa, babbb, aabbbb,
babaabb, babab, aabbab, babaaab}
  If L is a set of strings then by L* we mean the set of all finite strings
formed by concatenating words from L, where any string can be
used as we like, and NULL string is also included in the resultant
set.

Kleene Example:
 
 L = {a}
Closure
Ans: L* = {^, a, aa, aaa, aaaa,……}
 L = {ab}
Ans: L* = {^, ab, abab, ababab,…….}
 L = {a, b}
Ans: L* = {^, a, b, aa, bb, ab, ba, aaa,…….}
  If L is a set of strings then by L+ we mean the set of all finite strings
formed by concatenating words from L, where any string can be
used as we like, and NULL string is NOT included in the resultant
set.

Example:
Positive  L = {a}
 
Closure Ans: L* = {a, aa, aaa, aaaa,……}
 L = {ab}
Ans: L* = {ab, abab, ababab,…….}
 L = {a, b}
Ans: L* = {a, b, aa, bb, ab, ba, aaa,…….}
Thanks
Prof. Dhara Sapara