构造字母表Σ={0,1}上不含子串110的正则表达式遇自动判分错误求助

考虑字母表Σ={0,1}上的语言L = {w|w不含子串110}
编写对应的正则表达式

我给出的正则表达式为0*(10*10)*1*，但自动判分器判定错误，不清楚如何修正。

自动判分器结果 #

Running command: $ timeout 15 python3 unit_tests/unit_test_prob_1_18f.py
UNEXPECTED RESULT ON THESE INPUTS: ['10', '010', '100', '101', '0010', '0100', '0101', '1000', '1001', '1011', ...]
Test for: unit_test_prob_1_18f.py
    This test gave you 0 more points

自动判分器代码 #

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import os
import sys
from automata.fa.nfa import NFA
import re

sys.path.append(os.path.dirname(os.path.dirname(os.path.abspath(__file__))))

### Open files and populate lists ###
accept_file = open("unit_tests/inputs/1_6f_accepts.txt", "r")
reject_file = open("unit_tests/inputs/1_6f_rejects.txt", "r")
accept_list = accept_file.readlines()
reject_list = reject_file.readlines()

### Remove newlines ###
for i in range(len(accept_list)):
    accept_list[i] = accept_list[i][:-1]
for i in range(len(reject_list)):
    reject_list[i] = reject_list[i][:-1]

### Test Inputs ###
from prob_1_18f import prob_1_18f
test_machine = NFA.from_regex(prob_1_18f, input_symbols={'0', '1'})

UNEXPECTED = []

for w in accept_list:
    if w not in test_machine:
        UNEXPECTED.append(w)

for w in reject_list:
    if w in test_machine:
        UNEXPECTED.append(w)

### Not Allowing automata-lib Functions ###
pattern = "accepts_input|copy|read_input|read_input_stepwise|validate|iter_transitions|show_diagram|cardinality|clear_cache|complement|count_mod|count_words_of_length|difference|empty_language|from_finite_language|from_nfa|from_prefix|from_subsequence|from_substring|from_substrings|from_suffix|intersection|isdisjoint|isempty|isfinite|issubset|issuperset|iter_transitions|maximum_word_length|minify|minimum_word_length|nth_from_end|nth_from_start|of_length|predecessor|predecessors|random_word|read_input_stepwise|successor|successors|symmetric_difference|to_complete|to_partial|union|universal_language|validate|words_of_length|concatenate|edit_distance|eliminate_lambda|from_dfa|from_regex|intersection|iter_transitions|kleene_star|left_quotient|option|read_input_stepwise|reverse|right_quotient|shuffle_product|union|validate|from_dfa|from_nfa|iter_transitions|to_regex|validate|isequal|issubset|issuperset|validate"
with open("prob_1_18f.py","r") as file:
    for line in file:
        if re.search(pattern, line):
            print("automata-lib funcs not allowed for this assignment")
            print(f"-->{line[:-1]}")
            sys.exit(1)

if len(UNEXPECTED) > 0:
    print("UNEXPECTED RESULT ON THESE INPUTS: ", end="")
    if len(UNEXPECTED) > 10:
        print("[", end="")
        for i in range(9):
            print(f"\'{UNEXPECTED[i]}\'", end=", ")
        print(f"\'{UNEXPECTED[9]}\'", end=", ...]")
    else:
        print(str(UNEXPECTED))
    print()
    print(f"Test for: unit_test_prob_1_18f.py")
    print(f"    This test gave you 0 more points")

错误原因分析 #

当前正则0*(10*10)*1*存在两个致命问题：

1. 合法字符串被错误拒绝：(10*10)单元要求每个匹配块必须包含至少两个1（开头一个、结尾一个）和至少一个0，像10、010这类仅含单个1加0的合法字符串，无法匹配该单元，也无法被前后的0*或1*覆盖，因此被错误判定为不合法。
2. 非法字符串被错误接受：(10*10)可以匹配110（即1+0个0+10），而110是明确需要被拒绝的子串，导致非法字符串通过校验。

正确正则表达式 #

(0|10)*1*

正则逻辑说明 #

• (0|10)*：匹配任意数量的0或10组合，确保所有0要么单独出现，要么仅跟在单个1之后，从根源避免110子串的形成；
• 1*：匹配字符串末尾任意数量的连续1，因为连续1后面没有0，不会产生110子串。

该正则可以覆盖所有不含110的合法字符串，同时拒绝所有包含110的非法字符串。

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