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

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