Please show work and explain!!! The reversal, rev(w), of a string w = w_1 middot

Question

Please show work and explain!!!

The reversal, rev(w), of a string w = w_1 middot middot middot w_n is the string w_n middot middot middot w_1. The reversal rev(L), of a language L is {rev(w) w elementof L}. Prove that if L is regular, rev(L) is regular. A prefix of a string w is a string for which there exists a y elementof sigma* for which xy = w. The prefix language pref(L) is the set of strings {x elementof sigma*: x is a prefix of a string w element L}. Prove that if L is regular, pref(L) is regular.

Explanation / Answer

6)

a)

consider language L is regular... so build a DFA M for L...

now .in DFA M, make accepting state (final state)as initial state, initial state as final state...

now this new DFA M2 accepts only those strings which are the reverse of the strings that are accepted by DFA M...

The language recognized by DFA M2 is rev(L) = {rev(w):w belongs to L}

since we have build DFA for rev(L)... the language rev(L) is regular..

if L is not regular...rev(L) is also not regular..because can't build DFA

b)

let consider L is regular... now construct DFA M for L..

then..remove all states which are non reachable over L...

then ..add epsilon transistions from every non-final states to funal states.. this will result an NFA which recognizes the languages pref(L)

Since, we have build NFA for Language pref(L), the language is regular....

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---