Let L be the set of all strings that are not in the English language. Is L regular?

From textbook, would like some help?

Someone recommended to me to think about how regular and regular languages are closed under complement. I am not sure what he means and how this helps me.

Also strings are a series of letters not broken up by spaces. So a string cannot be a sentence, it has to a be a group of letters. I hope this clarifies any confusion.

  • $\begingroup$ By strings do you mean words? $\endgroup$ – Mariano Suárez-Álvarez Jan 21 '15 at 8:51
  • $\begingroup$ yes, strings also mean words $\endgroup$ – a b Jan 21 '15 at 8:51
  • $\begingroup$ «Also»? I mean: do you mean strings are English words,as opposed to, for example, sentences? $\endgroup$ – Mariano Suárez-Álvarez Jan 21 '15 at 8:52
  • $\begingroup$ Your textbook most probably explains that the complement of a regular language is regular somewhere. $\endgroup$ – Mariano Suárez-Álvarez Jan 21 '15 at 8:53
  • $\begingroup$ strings are not sentences, they are any group of letters not broken up by a space. It can spell out a word or it can spell out something random. Does that clarify? I don;t want to say word because it does not necessarily have to be an actual word $\endgroup$ – a b Jan 21 '15 at 8:54

The set of strings in the English language is presumably finite. Why don't you create a DFA to recognize all of them and then negate the acceptance?

Alternatively, create the regex of all English words: (Aardvard | .... | zymurgy) and take its complement.

  • $\begingroup$ Why is it finite? You can make countably many sentences like «One plus one plus one plus one is five». $\endgroup$ – Mariano Suárez-Álvarez Jan 21 '15 at 8:48
  • $\begingroup$ In fact, this website says that the number is bounded by 2 million. languagemonitor.com/number-of-words/… $\endgroup$ – Mark Jan 21 '15 at 8:49
  • 1
    $\begingroup$ @Mariano: The OP has now made it clear that the strings in question are lexical items, not sentences. The English lexicon at any given point in time is finite, hence regular. $\endgroup$ – Brian M. Scott Jan 21 '15 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.