Definition: A language, L, is finite if L contains a finite number of strings; otherwise, L is infinite.
Note: Let S be a set;
card(S) is the number of its members.
Examples:
• L1 = Æ is finite because card(L1) = 0
• L2 = {e } is finite because card(L2) = 1
• L3 = {x: |x| = 1} = {0, 1} is finite because
card(L3) = 2
• L4 = {x: 10 is substring
of x} = {10, 010, 100, … }
is infinite
Finite and Infinite
Languages
Gist:
finite language contains a finite number of strings
12/20