CODEWITHSUNDEEP
computation-theory
Debashree Bardhan
Debashree Bardhan

Reputation: 115

Regular language for number of A's in the string

L={w|w€{a,b}, number of a is divisible by 2 }is the language. Can someone help me with the regular grammer of this?

Upvotes: 2

Views: 136

Answers (1)

Patrick87
Patrick87

Reputation: 28302

The language is the set of all strings of a and b with an even number of a. This is a regular language and the goal is to produce a regular grammar for it.

Unless the regular grammar you're going to need is trivial, I would recommend always writing down the finite automaton first, and then converting it into a grammar. Converting a finite automaton into a grammar is very easy, and solving this problem is easy with a finite automaton. We will have two states: one will correspond to having seen an even number of a, the other an odd number. The state corresponding to having seen an even number of a will be accepting, and seeing b will not cause us to change states. The DFA is therefore:

       b         b
      /-\       /-\
      | V       | V
----->(q0)--a-->(q1)
        ^         |
        |    a    |
        \---------/

A regular grammar for this can be formed by writing the transitions down as productions, using the states as nonterminal symbols, and including an empty production for the accepting state:

(q0) -> b(q0) | a(q1) | e
(q1) -> b(q1) | a(q0)

For the sake of completeness, you could run some other algorithms on the grammar or automaton and get a regular expression, maybe like this: b*(ab*ab*)* (just wrote that down, not sure if it's right or not, left as an exercise).

Upvotes: 1

Related Questions