[antshockey]

Hi guys,
I am just doing some revision for an upcoming exam on language design.
I came across the question:
Write a regular expression for all words where all the letters occur in alphabetical order.

I have written down:

a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*

Which I am pretty sure is right, it just seems too simple for the amount of marks it's worth.
Any help will be appreciated.
Thanks

[Motoma]

Looks good to me.

[antshockey]

Thanks, I just needed some clarification considering the hardest part was getting the alphabet in the right order haha.

[antshockey]

It should be noted for future browsers that this expression allows the creation of words that have a total of 0 letters.

[Karel-Lodewijk]

Quote

It should be noted for future browsers that this expression allows the creation of words that have a total of 0 letters.

If this is formal languages, then the empty string (epsilon) is a word over any alphabet.

This post has been edited by Karel-Lodewijk: 24 January 2012 - 07:21 PM

[Nikitin]

Karel-Lodewijk, on 24 January 2012 - 08:19 PM, said:

Quote

It should be noted for future browsers that this expression allows the creation of words that have a total of 0 letters.

If this is formal languages, then the empty string (epsilon) is a word over any alphabet.

But that has nothing to do with actually belonging to a specific language. In this language, the epsilon does belong to it (which was the point of that post).

[Karel-Lodewijk]

Nikitin, on 25 January 2012 - 06:51 AM, said:

Karel-Lodewijk, on 24 January 2012 - 08:19 PM, said:

Quote

It should be noted for future browsers that this expression allows the creation of words that have a total of 0 letters.

If this is formal languages, then the empty string (epsilon) is a word over any alphabet.

But that has nothing to do with actually belonging to a specific language. In this language, the epsilon does belong to it (which was the point of that post).

Well obviously the letters of the empty string are in alphabetic order due to there not being any, so it is also part of the language defined. Didn't think there was room for any confusion there.

I just responeded to

Quote

It should be noted for future browsers that this expression allows the creation of words that have a total of 0 letters.

It seemed to imply that it was some kind of error in the regular expression, while this is desired behavior.

This post has been edited by Karel-Lodewijk: 25 January 2012 - 11:17 AM

[antshockey]

Because the question stated find all words. I thought I'd point it out.
Basically words can't have 0 letters.
They might technically be right in Regular Expression terms but they are still non-existent in actual language.

[Karel-Lodewijk]

antshockey, on 25 January 2012 - 06:38 PM, said:

Because the question stated find all words. I thought I'd point it out.
Basically words can't have 0 letters.
They might technically be right in Regular Expression terms but they are still non-existent in actual language.

If we are talking about formal languages, then I disagree, this is exactly why I made the comment.

I say the empty string is a word and is part of the language.

In short, a formal language is a set of strings/words over an alphabet, the empty string is a string/word over any alphabet.

Formal languages can be expressed in many ways, regular expression and plain English being two of them, both the representations are in your original post.

If you express the language as a regular expression, then the empty string is a part of it as you pointed out.

If I look at the assignment, the plain English representation is:

Quote

Words where all the letters occur in alphabetical order.

Is the empty string a word -> Check
Do the letters of the empty string appear in alphabetical order -> Check

Basically every statement you make about the letters of the empty string will logically be true because there are no letters in the empty string.

http://en.wikipedia....Formal_language
http://en.wikipedia....egular_language

I probably should have been more through in my response in the first place, sorry for the confusion.

This post has been edited by Karel-Lodewijk: 25 January 2012 - 04:10 PM