CFG for strings with unequal numbers of a and b – Context-free grammar.

CFG for strings with unequal numbers of a and b

Rules:   

S                     U|V                                                              Rule 1

U                   TaU|TaT                                                       Rule 2

V                    TbV|TbT                                                      Rule 3

T                    aTbT|bTaT|epsilon                                    Rule 3

 

Proof:    (for invalid strings)

1-For String baba

S                     V                                                             (by rule 1)

S                     TbT                                                         (by rule 3)

S                     (epsilon)b(aTbT)                                  (by rule 4)

S                     ba(T)b(T)

S                     ba(epsilon)b(aTbT)                               (by rule 4)

S                     baba(T)b(T)

S                     baba(epsilon)b(epsilon)                       (by rule 4)

S                     babab                                                      (by rule 4)

True because these rules  can not produce invalid string. It is producing valid string.

2-For String abbaba

S                     U                                                               (by rule 1)

S                     TaT                                                            (by rule 2)

S                     (epsilon)a(bTaT)                                      (by rule 4)

S                     ab(T)a(T)

S                     ab(bTaT)a(T)                                            (by rule 4)

S                     abb(T)a(T)a(T)

S                     abb(epsilon)a(bTaT)a(epsilon)              (by rule 4)

S                     abbab(T)a(T)a                                           (by rule 4)

S                     abbab(epsilon)a(epsilon)a                     (by rule 4)

S                     abbabaa

True because these rules  can not produce invalid string. It is producing valid string.

 

Proof:    (for valid strings)

1-For String babab

S                     V                                                                   (by rule 1)

S                     TbT                                                               (by rule 3)

S                     (epsilon)b(aTbT)                                        (by rule 4)

S                     ba(T)b(T)

S                     ba(epsilon)b(aTbT)                                    (by rule 4)

S                     baba(T)b(T)

S                     baba(epsilon)b(epsilon)                            (by rule 4)

S                     babab                                                           (by rule 4)

True because these rules  produces valid string.

2-For String abbabaa

S                     U                                                                   (by rule 1)

S                     TaT                                                                (by rule 2)

S                     (epsilon)a(bTaT)                                         (by rule 4)

S                     ab(T)a(T)

S                     ab(bTaT)a(T)                                                (by rule 4)

S                     abb(T)a(T)a(T)

S                     abb(epsilon)a(bTaT)a(epsilon)                 (by rule 4)

S                     abbab(T)a(T)a                                              (by rule 4)

S                     abbab(epsilon)a(epsilon)a                        (by rule 4)

S                     abbabaa

True because these rules  produces valid string.

 

CFG for strings with unequal numbers of 0 and 1

Rules:   (correct one)

S                     U|V                                                              Rule 1

U                   T0U|T0T                                                       Rule 2

V                    T1V|T1T                                                      Rule 3

T                    0T1T|1T0T|epsilon                                    Rule 3

More Examples of CFG

1. 1. Intro to Context Free Grammar with 12 Examples
   2. CFG of Language of all even and odd length palindromes
   3. Context Free Grammar CFG for language of all even length strings
   4. CFG for the language of all non Palindromes
   5. CFG for strings with unequal numbers of a and b
   6. CFG of odd Length strings {w | the length of w is odd}
   7. CFG of Language contains at least three 1’s or three a’s {w | w contains at least three 1’s}
   8. CFG for the language L = 0ⁿ1ⁿ where n>=1
   9. CFG for the language L = 0ⁿ1²ⁿ where n>=1
   10. Write a CFG for the language L = 0ⁿ1⁴ⁿ where n>=1