質問

I'm just kind of confused about regular expressions. Can there be a regular expression that recognizes an infinite language or do all regular expressions recognize finite languages?

役に立ちましたか?

解決

It is definitely possible to build regular expressions that recognize infinite languages. For example, the simple regular expression a* matches the infinite language

{ ε, a, aa, aaa, aaaa, ... }

The star operator is essential in regular expressions to enable them to recognize infinite sets of strings.

It is true that all finite languages are regular, but not all regular languages are finite (as shown above). Formal language theory tells us that there are a lot of languages that are infinite but not regular (such as {0n1n | n ≥ 0}), though, so you can't always write a regular expression for an arbitrary infinite langugage.

Hope this helps!

ライセンス: CC-BY-SA帰属
所属していません StackOverflow
scroll top