Regular Expression

[zombiegirl]

HI All, :D I'm computer science student. Would you like to tell me about that problem? Here.
1) RE for accepts all strings of (a,b,c) that contains an odd number of a's.
2)Re for the language of all binary of strings that have at least three symbols and whose first and last symbols are different.
3)
Simplify the following REs (that is ,find the simpler RE for the same language):
a.(r + Є)*,
b.SS*+Є ,
c.(Є+r)(r+s)*(Є+r),
d.(r+s+rs+sr)*
:blink:

The hint also okay for me.
Thanks.

[Rashakil Fol]

How much time you have spent on these problems?

[zombiegirl]

Now I got it thanks Rashakil Fol . But I have a lot of questions in Regular Languages.
1) Show that the set of regular languages is closed under reversal. That is,if L is the regular, then so is { x R :x € L} where x R denotes the reversal of string r.
2)Give the example to show each of following for the language L1 and L2:
a)If L1 belongs to L2 and L2 is regular ,then L1 can be regular or nonregular.
b)If L1 and L2 are nonregular,then L1∏L2 can be regular or nonregular.
c)If L1 and L2 are nonregular,then L1 U L2 can be regular or nonregular.
3)Suppose language L is accepted by FA M.Let L E be the subset of L consisting of those strings in L of even length.Show how to convert M to an FA for L E.
4)Prove the set of all strings of a and b with more a’s than b’s is nonregular.
5)For each of the following languages ,state whether it is regular or not .If not ,give a proof that it is nonregular.
a)The set of binary strings with equal number of occurrences of the substring 01 and 10.
b)The set of binary nonpalindromes.
Help me please. Thanks for your time.
c){a2 n:n>0}
Let us use the notation x = L y to mean the strings x and y are indistinguishable with respect to language L.
a) Show that =L is an equivalence relation that is for all stings x,y,z the following hold
(i)x=Lx
(ii)If x=Ly ,then y=L x
(iii)if x=L y and y =L z ,then x= L z
b)Show that =L is the right congruence ,that is , for all the string x,y,z the following holds:
If x=Ly then xz=Lyz.

[popin]

go away google regular expressions + the language your codeing(sp?) in and maybe crack open the text book thats 1st on the recommended reading list for your class, its really not that complicated the main part of the programs going to be the same each time (namely processing the string character by character and performing analysis on it, you just have to modify the peramiters each time. Anyway try it yourself people don't like doing your homework for you if your still stuck come bac post here asking about what your stuck with (not the whole dahm assignment) and what language your using.

[zombiegirl]

a) L1={empty set } << regular
l2={0,1}
L1 belongs to L2.so L1 can be regular.
b)The intersection of a non-regular language and its complement is empty, and the
empty language is regular.
c)The Union of any languages and it's complements is Ʃ * which is regular.
Correct me if I wrong and still thinking about others.
Thanks.

[AuburnMathTutor]

These are to be construed as hints; you must still show the work involved in actually solving the problem.

1) Show that the set of regular languages is closed under reversal. That is,if L is the regular, then so is { x R :x € L} where x R denotes the reversal of string r.

Hint: Every regular language is accepted by some NFA, and every language accepted by an NFA is a regular language. Assume an NFA for L, and describe how you would construct the NFA for rev(L).

2)Give the example to show each of following for the language L1 and L2:

a)If L1 belongs to L2 and L2 is regular ,then L1 can be regular or nonregular.

S* is a regular language.

b)If L1 and L2 are nonregular,then L1∏L2 can be regular or nonregular.

The empty language is regular.

c)If L1 and L2 are nonregular,then L1 U L2 can be regular or nonregular.

L union complement(L) = S*

3)Suppose language L is accepted by FA M.Let L E be the subset of L consisting of those strings in L of even length.Show how to convert M to an FA for L E.

What if you broke each state Q into two states Q_E and Q_O?

4)Prove the set of all strings of a and b with more a’s than b’s is nonregular.

Pumping lemma for regular languages.

5)For each of the following languages ,state whether it is regular or not .If not ,give a proof that it is nonregular.

a)The set of binary strings with equal number of occurrences of the substring 01 and 10.

Pumping lemma for regular languages. Perhaps (01)^n(10)^n?

b)The set of binary nonpalindromes.
Help me please. Thanks for your time.

The complement of a regular language is a regular language.

c){a2 n:n>0}

No idea what that means.

Let us use the notation x = L y to mean the strings x and y are indistinguishable with respect to language L.

a) Show that =L is an equivalence relation that is for all stings x,y,z the following hold
(i)x=Lx
(ii)If x=Ly ,then y=L x
(iii)if x=L y and y =L z ,then x= L z

Use the definition of =L, whatever one you're using. Post your definition if you want more help. Is it delta*(Q,w)?

b)Show that =L is the right congruence ,that is , for all the string x,y,z the following holds:
If x=Ly then xz=Lyz.

Again, use the definition of =L. Probably a delta*(Q,w)-esque definition.

Disclaimer: I take no responsibility for the appropriateness of these hints. These are offhand and upon actually doing the problem I might realize that changing tacts is in order.

[zombiegirl]

Thanks for your hints. You make my day.