Question

Let L be the language over {a, b, c, d} accepting all strings so that: 1. All c's occur before the first b. 2. All d's occur after the first b. 3. The last symbol of the string is a. 4. Each a that is not the last symbol is immediately followed by an even number of d's.

Choose any constructive method you wish, and demonstrate that Lis regular. You do not need an inductive proof, but you should explain how your construction accounts for each rule.

Answer 1

We made use of the Regular expression and justification as a constructive method that showed that L is regular.

Step-by-step explanation:

Solution

Regular Expression:

( c + a )* b d*( a (dd)* + bd*)* a

Justification:

All c's occur before the first b, there can be a's as well

So, we have (c + a)*

(dd)* for even number of d's