Language | Theory of Computation
  • Definition − A language is a subset of ∑* for some alphabet ∑. It can be finite or infinite.
  • Example − If the language takes all possible strings of length 2 over ∑ = {a, b}, then L = { ab, bb, ba, bb}
  • Example - Suppose we have the following grammar:

G: N={S, A, B} T= {a, b} P= {S →AB, A →aA|a, B →bB|b}


The language generated by this grammar:

L(G) = {ab, a2b, ab2, a2b2, ………} = { am bn | m ≥ 0 and n ≥ 0}

Null Set | Theory of Computation

i.    Null set is the unique set having no elements; its size or cardinallity (count of elements in a set) is zero.

ii.    The null set, also called the empty set, is the set that does not contain anything.

iii.    It is symbolized { }.

iv.    A null set can contain a null string.

Lakshay Kakkar @lakshay7k
31 Jul 2018 09:48 pm
Kindly make a correction in 4th point. Null set can't contain null string.
Ram Kumar @kamitube
1 Aug 2018 10:49 pm
Akshaya Kumar Biswal @akshayakumarbis
10 Aug 2018 01:36 pm
thank you for the feedback