Jump to content

Talk:Star-free language

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

I don't understand how the language described in this article can be star-free. It can include strings of arbitrary length, so how can its regular expression possibly NOT require a Kleene star? 87.112.197.217 (talk) 19:17, 2 October 2011 (UTC)[reply]

I agree with the above comment. The "For example" is unclear: is it an example of a language that is or is not star-free? If star-free, then why does it use a construct (complement) that is not in the definition given in the previous sentence? I recommend that the "For example" sentence be removed, or completely rewritten. Mdernst (talk) 19:27, 19 October 2011 (UTC)[reply]

"All Boolean operators" refers to union, intersection and complement. You can see this from following the wikilink. However, I have added this explicitly to the lede. Hermel (talk) 21:53, 20 October 2011 (UTC)[reply]

Location in Chomsky hierarchy

[edit]

In order to establish the location of the class of star-free languages in the (extended) Chomsky hierarchy (shown in the template at page bottom), could somebody give a (sourced) example of a regular language that is not star-free? - Jochen Burghardt (talk) 11:05, 25 February 2015 (UTC)[reply]

I've added one. Tim Smith (talk) 12:24, 8 October 2015 (UTC)[reply]