Hi, I am having trouble answering the following question. a) If L is a language

Question

Hi,

I am having trouble answering the following question.

a)

If L is a language and a is a symbol, then the language denoted as "L/a" is defined as follows:

L/a = {w | wa ? L}

Informally put, L/a can be generated from L as follows: enumerate all the strings in L that end with the symbol 'a', then remove that 'a' from those strings, and output the rest of the strings.

For example, if L = {0,001,100}, then L/0 = {?,10} and L/1 = {00}.

The question for this problem is as follows: If you are given that L is regular, then show that L/a is also regular. Your answer should be generic (and not based on a specific example). An example approach would describe a method to construct a finite automation for L/a from a deterministic finite automata corresponding to L.

b)

Now, let us define another language called "aL" as follows:

aL = {w | aw ? L}

For example, if L = {0,001,100}, then 0L = {?,01} and 1L = {00}.

Using the result proven in part (a) and any other closure properties of regular languages, show that aL is regular if L is regular.

Any help you can provide would be very much appreciated.

Explanation / Answer

a)

if L is regular then L/a is also regular this can be done by constructing a DFA same as for L and make few changes

every state from which after reading symbol ' a ' we reach final state then make that state as final and make every previous final state to non final expect if that state on reading ' a ' come to itself

b)

if L and M are a regular language then L/M is also regular language

a is a regular language we can construt a DFA for that and if a/L is also regular then L must be regular language

=>a/L is regular if L is a regular language

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.