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.

Question

Paulina

Computers & Technology

22 November, 11:57

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.

+5

Answers (1)

Know the Answer?

Jocelyn Fry · Answer 1

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

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