[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 121 KB, 450x523, turing.jpg [View same] [iqdb] [saucenao] [google]
6631192 No.6631192 [Reply] [Original]

What is meant by the set of regular expressions over the language {0,1}?

>> No.6631196

If you are too lazy or too unintelligent to look up the definition of "regular expression", then drop the fuck out. Stop polluting the academic environment of your university. You don't belong there.

>> No.6631228

>>6631196
Sigh.

>> No.6631239

>>6631192
all the regular expressions built with this 2-elemetns alphabet.

Like
1(00)*
0(00)*(1+01)+1
(0+1)*(00) + (0+1)* (010) (0+1)* )
...
for instance

exercise : what does this last regexp denotate?

>> No.6631300

>>6631239
Thanks. This is what I wanted to confirm.

The last regular expression is malformed. One too many ). Otherwise it would be all 0 and 1 strings ending with 00 or containing 010.

The extra ) is a clue as to why the set of regular expressions over the language {0,1} does not form a regular language.

Exercise: prove it. :)

>> No.6631304

>>6631300
This is b8.

>> No.6631307

>>6631300
Sorry, I meant to say the alphabet {0,1} all along.

>> No.6631313

>>6631307
That's the least significant of your mistakes / bait attempts.

>> No.6631321

>>6631313
What did I do wrong? The b8 is a lie.

>> No.6631345

>>6631300
>(0+1)*(00) + (0+1)* (010) (0+1)*
>it would be all 0 and 1 strings ending with 00 or containing 010.
nope
if + is kleene plus 01010 (contain 010) and 100 (end in 00) are not recognized even if they respect your specification.

>> No.6631348

>>6631300
>The extra ) is a clue as to why the set of regular expressions over the language {0,1} does not form a regular language.
what? explain please

>> No.6631368

Why is sci so slow tonight?

>> No.6631384

>>6631300
> The set of regular expressions do not form a regular language
> blah regular blah blah do not regular blah blah
> regular not regular

>> No.6632044

>>6631345
>if + is kleene plus 01010 (contain 010) and 100 (end in 00) are not recognized even if they respect your specification.

I'm pretty sure + is meant to be union in this context.

>> No.6632048
File: 148 KB, 409x326, 1337082139544.png [View same] [iqdb] [saucenao] [google]
6632048

>mfw first year CS students
This retard is trolling, but there are enough of these people who spout shit like this and think they are mathematical geniuses. Why is CS so horrible?

>> No.6632051

>>6631348

Assume that the regular expressions over the alphabet {0,1} does form a regular language L. Then it must contain a string w = (^Na)^N which represents N left brackets followed by N right brackets, as long as N >= 0, right?

So, by the pumping lemma we should be able to pump a substring of the left, a^N, brackets and still get a w in L, which is not possible since you end up with with more left brackets than right brackets, no matter what N is - as long as you can pump it.

>> No.6632061

>>6632048

/sci/ has really gone down the drains. You people are ruined by this place.

>> No.6632870

>>6632048
>>6632061
>CS is horrible

I still don't understand why people talk shit about CS as a field, when the problem is the people currently studying it. I'm not a CS (more of a CE/EE, but did some OS research, which can happen to be kind of on the line between CS and CE/EE), but what little I've delved into the field and what little theoretical CS-related research I did for CS professors as an undergrad clearly tells me it's a respectable field on it's own. It's, unfortunately, polluted by unmotivated neckbeards and bros, but that's the educational system's fault, not the field's.

Blame people, not the field. The professors I had the fortune of working with were brilliant, as were the PhD students and undergrad students who were doing research out of genuine interest.

It's the students fault for wanting everything to be easy and for studying a science and achieving barely passing marks on everything and learning the bare minimum to land an IT job they could've just gone to trade school for. We've got similar types in EE who stay on controllers and nothing else. Controllers are cool and all, but where's the interest on digital signal processing? Energy Systems? Semi Conductors? I'll tell you where it is, only the handful who are truly passionate delve into those because the rest just tailor their curriculum so that they can graduate with the bare minimum necessary to get a job as an industry grunt and avoid the stuff they deem "too hard", much like the CS tadpoles.