L = {w|w 的正则表达式不包含字母表上的子串 110} Σ = {0,1}

Question

考虑语言 L = {w|w 不包含字母表 Σ = {0,1} 上的子串 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]}\

Answer 1

您的正则表达式接受

110

，（特别是

10*10

部分，其中

0*

接受 ε）。

没有出现

110

相当于说在第一次出现

11

（如果有的话）之后，输入的其余部分中不应再有零。

所以我们可以使用这个正则表达式：

(0|10)*1*