CODEWITHSUNDEEP
regexregular-languagefinite-automata
user1680944
user1680944

Reputation: 567

Is it possible to express a language with infinite number of strings using a finite regular expression?

I am trying to understand how to generate a regular expression for some grammars that I suppose are kind of "Infinite". I have the following a Σ = {0,1} I thought of the following three cases and here are the guesses that I gave.

  1. The set of all strings with 0 and ending in 11. The regular expression that I have is the following: 0+ [1*] [0*] 1+ 1. However, I know that this expression won't cover all the set of the existing strings in that set.
  2. The set of all strings containing at least two consecutive 1s. The regular expression that I have is the following: 1 1+ [0+] [1+] 1. Same issue as the first point.
  3. The set of all strings beginning with 0s and not having two consecutive 1s. The regular expression that I have is the following: 0+ 1 0+ 1 [0+]. Same issue as the first and second point.

My question is the following: Is there a possibility to express these languages that have infinite number of strings with a finite regular expression. If yes, how exactly? Thank you.

Upvotes: 0

Views: 384

Answers (1)

lodo
lodo

Reputation: 2383

Yes, ANY regular language can be recognized by a finite automaton, and a regular language MAY express an infinite number of matching strings. Addressing your three examples:

  1. 0 (0|1)* 1 1
  2. (0|1)* 1 1 (0|1)*
  3. 0+ (1 0+)+ 1?

Upvotes: 3

Related Questions