Proving language is regular

0
votes

Let Σ be a finite alphabet and L ⊆ Σ be a language. Let Σ0 ⊆ Σ. For each string w = w1 · · · wn ∈ Σ , define res(w, Σ 0 ) = y1 · · · yn where yi = wi if wi ∈ Σ 0 , and yi = if wi ∈ Σ \ Σ 0 , for each 1 ≤ i ≤ n. (For example res(abracadabra, {a, b}) = abaaaba.) Then define res(L, Σ 0 ) = {res(w, Σ 0 ) : w ∈ L}

I have a very general direction and thought process for these problems, however, i am not completely sure i could construct a viable proof for the following problems. If anyone could point me in the right direction, that would be much appreciated.

(a) Show that if L ⊆ Σ* ? is regular and Σ0 ⊆ Σ, res(L, Σ 0 ) must be regular.

i know for this one, a DFA cannot be made for this language. So i will have to figure out a different way. A subset of any regular language is not necessarily regular.

(b) Show that if L ⊆ Σ* is context-free and Σ0 ⊆ Σ, res(L, Σ 0 ) must be context-free.

I know that for this problem, one way to solve it would be to provide a context free grammar

(c) Show that if L ⊆ Σ* and res(L, Σ 0 ) is regular whenever Σ0 ⊂ Σ, L need not be regular.

For this question, we can say that even if L is not regular, that the empty language is a regular subset of this language. This would be true in all languages (whether it is regular or not)

2
context-free-grammarcomputation-theorydfanfa
If you want help with your homework, at least show some evidence that you've tried and ask about specific sub-problems. Just pasting in four problems and saying "I think I have an idea, but please tell me the answer" is unlikely to attract any positive attention! – dovetalk
Do you really mean that L is a subset of the alphabet? – John Coleman
@JohnColeman yes, that is what the assignment actually states. – CS959595
@CS959595 It is almost certainly a typo since that would make little sense. – John Coleman
@JohnColeman Thats what i initially thought, however, after asking my professor, i was told it was actually intended. – CS959595

2 Answers

0
votes

I'm working on this question as well, here were my thoughts

for a: if L is regular, it can be represented by a regular expression, so it should be possible to make a regular expression for L'.

for b: make a CFG where the terminals found in V and R of {V,E',R,S} just includes the terminals of E'

for c: assume that res(L, E') is regular, so as long as the alphabet is a true subset in that it can not equal the alphabet of L. L does not need to be regular.

These are just my initial thoughts, so take them with a grain of salt (maybe someone else can provide feedback)

0
votes

While its evident that this is a homework assignment, a suggestion for part (a) is to look into closure properties for regular languages.

Take a look at L, the provided language in res(L, Σ’). Now take a look at the language (lets call it L') over the alphabet Σ’.

Now lets look at your example:

res(abracadabra, {a, b}) = abaaaba

In this scenario, L ∈ { abracadabra } and L' ∈ { abaaaba }

Between these two languages, L and L', what standard set operation can we use to create a set of only the elements each language has in common?

If you took a look at closure properties for regular languages, I'm sure you'll see the perfect fit!