DFA转RE技术咨询：特定语言正则表达式正确性验证

First, let's restate the language we're targeting clearly:

Strings over Σ = {0,1,2} where the last character is not less than the first character. Valid examples: 0, 2012, 102; Invalid examples: 10, 2021.

Your regex is:

(0(0+1+2)* )(1(0(1+2)+1+2)* )(2((0+1)2+2))*)

Key Issues with Your Regex #

1. Fundamental Structural Error: Incorrect Combination of Branches #

Your regex concatenates three separate parts ((0...) (1...) (2...)) instead of using alternation (+ in regex notation for finite automata) to represent the three valid cases of the language.

Right now, your regex only matches strings that:

• Start with 0 (from the first part),
• Followed by a string starting with 1 (second part),
• Followed by a string starting with 2 (third part).

This means it can't match valid strings like 1 (single character), 11, 22, or 01—all of which should be accepted by the language.

2. Incorrect Handling for Strings Starting with 1 #

For strings starting with 1, the last character must be 1 or 2 (since 1 ≤ 1 and 1 ≤ 2). Your second part 1(0(1+2)+1+2)* only allows sequences where every non-leading character is either:

• 0 followed by 1/2,
• Or a single 1/2.

This fails to match valid strings like 1001 (starts with 1, ends with 1, but the middle 00 isn't allowed by your pattern).

3. Incorrect Handling for Strings Starting with 2 #

For strings starting with 2, the last character must be 2 (since 2 can't be less than any other character). Your third part 2((0+1)2+2)* only allows sequences where every non-leading character is either:

• 0/1 followed by 2,
• Or a single 2.

This fails to match valid strings like 2002 (starts with 2, ends with 2, but the middle 00 isn't permitted by your pattern). Also, your third part has a syntax error—an extra closing parenthesis ())*) instead of )*).

Correct Regular Expression for the Language #

We can split the language into three mutually exclusive cases, then combine them with alternation:

1. Case 1: First character is 0
   The last character can be 0, 1, or 2 (since 0 ≤ all characters in Σ). This covers strings starting with 0, followed by any sequence of characters (including none), ending with any character.
   Pattern: 0(0+1+2)* (this part of your original regex was correct!)

2. Case 2: First character is 1
   The last character must be 1 or 2. This includes single character 1, plus strings starting with 1, followed by any sequence of characters, ending with 1 or 2.
   Pattern: 1(0+1+2)*(1+2) + 1
   Can be simplified to: 1( (0+1+2)*(1+2) | ε ) (where ε represents the empty string)

3. Case 3: First character is 2
   The last character must be 2. This includes single character 2, plus strings starting with 2, followed by any sequence of characters, ending with 2.
   Pattern: 2(0+1+2)*2 + 2
   Can be simplified to: 2( (0+1+2)*2 | ε )

Combining all three cases with alternation gives the final correct regex:

0(0+1+2)* + 1((0+1+2)*(1+2) | ε) + 2((0+1+2)*2 | ε)

Or, if we want to write it without explicit ε (using the fact that (0+1+2)* includes the empty string when we adjust the pattern):

0(0+1+2)* + 1(0+1+2)*(1+2)? + 2(0+1+2)*2?

(Note: ? here represents "zero or one occurrence", which is equivalent to | ε in regex notation for finite automata.)

内容的提问来源于stack exchange，提问作者Andreea Mitel