| Prev | Next |
Regular Grammar
A regular language can also be described using regular grammar which is basically a set of rules using a set of terminals and non-terminals. The terminals are basically the elements of the alphabet Σ and the non-terminals, also referred to as variables, are a composition of terminals and non-terminals. More formally,
Definition: A regular grammar G is a 4-tuple (V, T, P, S).
- V → Variables/Non-terminals that correspond to states Q
- T → Terminals that correspond to the alphabet Σ
- P → Productions/rules that correspond to transitions δ
- S → Start rule that corresponds to the initial state.
Regular expressions and their equivalent grammar
a? → Strings with 0 or 1 a. L = {ε, a}
S → a | ε
a* → Strings with 0 or more a's. L = {ε, a, aa, aaa, ...}
S → aS | ε OR alternately, S → Sa | ε
a+ → Strings with 1 or more a's. L = {a, aa, aaa, ...}
S → aS | a
a+b → Either a or b. L = {a, b}
S → a | b
(a+b)(a+b) → Combination of a or b of length 2. L = {aa, ab, ba, bb}
S → aA | bA
A → a | b
(a+b)* → Strings with any combination of a's and b's. L = {ε, a, b, aa, ab, ba, bb, aaa, ...}
S → aS | bS | ε
(a+b)*abb → Strings ending with abb. L = {abb, aabb, babb, aaabb, ababb, baabb, bbabb, ...}
S → aS | bS | aB
B → bA
A → b
ab(a+b)* → Strings starting with ab. L = {ab, aba, abb, abaa, abab, abba, abbb, ...}
S → aB
B → bA
A → aA | bA | ε
(a+b)*aa(a+b)* → Strings that contains aa. L = {aa, aaa, baa, aab, ...}
S → aS | bS | aA
A → aB
B → aB | bB | ε
a*b*c* → 0 or more a's, followed by 0 or more b's, followed by 0 or more c's. L = {ε, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, ...}
S → aS | bB | cC | ε
B → bB | cC | ε
C → cC | ε
a+b+c+ / aa*bb*cc* → 1 or more a's, followed by 1 or more b's, followed by 1 or more c's. L = {abc, aabc, abbc, abcc, aabbc, aabcc, abbcc, ...}
S → aA
A → aA | bB
B → bB | cC
C → cC | ε
(a+b)*(a+bb) → Strings that end with a or bb. L = {a, bb, aa, abb, ba, bbb, ...}
S → aS | bS | a | bB
B → b
(aa)*(bb)*b → Strings with even number of a's followed by odd number of b's. L = {b, aab, bbb, aabbb, ...}
S → aA | bB | ε
A → aC
C → aA | bB | ε
B → bD | ε
D → bB
(0+1)*000 → Binary strings ending with 3 0's. L = {000, 0000, 1000, 00000, 01000, 10000, 11000, ...}
S → 0S | 1S | 0A
A → 0B
B → 0
(11)* → Strings with even number of 1's. L = {ε, 11, 1111, 111111, ...}
S → 1A | ε
A → 1S
01* + 1 → {1} U Strings the start with 0 followed by zero or more 1's. L = {1, 0, 01, 011, ...}
S → 0A | 1
A → 1A | ε
(01)* + 1 → {1} U Strings with zero or more 01's. L = {1, ε, 01, 0101, 010101, ...}
S → 0A | 1 | ε
A → 1B
B → 0A | ε
0(1* + 1) → 0 followed by any number of 1's. L = {0, 01, 011, 0111, ...}
S → 0A
A → 1A | ε
(1+ε)(00*1)*0* → Strings with no consecutive 1's. L = {ε, 1, 10, 101, 1001, 1010, 10101, 101001, 101010, ...}
S → 1A | 0B
A → 0B
B → 0B | 1C
C → 0B | 0D | ε
D → 0D | ε
Exercises
Hopefully you got the hang now. For the regular expressions given below try to come up with the grammar.1. a's and b's of length 2
aa + ab + ba + bb OR (a+b)(a+b)
2. a's and b's of length ≤ 2
ε + a + b + aa + ab + ba + bb OR (ε + a + b)(ε + a + b) OR (a+b)? (a+b)?
3. a's and b's of length ≤ 10
(ε + a + b)10
4. Even-lengthed strings of a's and b's
(aa + ab + ba + bb)* OR ((a+b)(a+b))*
5. Odd-lengthed strings of a's and b's
(a+b) ((a+b)(a+b))*
6. L(R) = { w : w ∈ {0,1}* with at least three consecutive 0's }
(0+1)* 000 (0+1)*
7. Strings of 0's and 1's with no two consecutive 0's
(1+ 0 1*)* OR (11* 0 1*)* OR (1 + 01)* (0 + ε)
8. Strings of a's and b's starting with a and ending with b.
a (a+b)* b
9. Strings of a's and b's whose second last symbol is a.
(a+b)* a (a+b)
10. Strings of a's and b's whose third last symbol is a and fourth last symbol is b.
(a+b)* b a (a+b) (a+b)
11. Strings of a's and b's whose first and last symbols are the same.
(a (a+b)* a) + (b (a+b)* a)
12. Strings of a's and b's whose first and last symbols are different.
(a (a+b)* b) + (b (a+b)* a)
13. Strings of a's and b's whose last and second last symbols are same.
(a+b)* (aa + bb)
14. Strings of a's and b's whose length is even or a multiple of 3 or both.
R1 + R2 where R1 = ((a+b)(a+b))* and R2 = ((a+b)(a+b)(a+b))*
15. Strings of a's and b's such that every block of 4 consecutive symbols has at least 2 a's.
(aaxx + axax + axxa + xaax + xaxa + xxaa)* where x = (a+b)
16. L = {anbm : n ≥ 0, m ≥ 0}
a* b*
17. L = {anbm : n > 0, m > 0}
aa* bb* OR a+b+
18. L = {anbm : n + m is even}
aa* bb* + a(aa)* b(bb)*
19. L = {a2nb2m : n ≥ 0, m ≥ 0}
(aa)* (bb)*
20. Strings of a's and b's containing not more than three a's.
b* (ε + a) b* (ε + a) b* (ε + a) b*
21. L = {anbm : n ≥ 3, m ≤ 3}
aaa a* (ε + b) (ε + b) (ε + b)
22. L = { w : |w| mod 3 = 0 and w ∈ {a,b}* }
( (a+b)(a+b)(a+b) )*
23. L = { w : na(w) mod 3 = 0 and w ∈ {a,b}* }
b* a b* a b* a b*
24. Strings of 0's and 1's that do not end with 01
25. L = { vuv : u, v ∈ {a,b}* and |v| = 2}
(aa + ab+ ba + bb) (a+b)* (aa + ab + ba + bb)
26. Strings of a's and b's that end with ab or ba.
(a+b)* (ab + ba)
27. L = {anbm : m,n ≥ 1 and mn ≥ 3}
a bbb b* + aaa a* b + aa a* bb b*