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}