图上作业法构造与DFA等价正规表达式的程序实现

要实现图上作业法构造与DFA等价正规表达式的程序，可以按照以下步骤进行：

1. 定义状态和转移函数的数据结构。可以使用字典或类等方式来表示。

2. 读入DFA的状态和转移函数信息，存入数据结构中。

3. 使用图上作业法构造正规表达式。具体步骤如下：

a. 为每个状态构造一个正则表达式，初始化为该状态自身。

b. 对于每个状态s，对于其所有出边(t, a)，将状态t的正则表达式加上a，得到新的正则表达式。

c. 对于每个状态s，对于其所有入边(t, a)，将状态t的正则表达式加上a*，得到新的正则表达式。

d. 重复步骤b和c，直到所有状态的正则表达式不再变化为止。

4. 输出每个状态的正规表达式即可。

下面是一个Python示例代码，假设DFA状态用数字表示，转移函数用字典表示，其中key为起始状态，value为一个字典，其中key为转移字符，value为到达的状态。为了简化代码，这里省略了读取DFA信息的部分，直接给出了数据结构。

def construct_regex(dfa):
    # 初始化每个状态的正则表达式
    regex = {}
    for state in dfa:
        regex[state] = str(state)

    # 重复进行步骤b和c，直到所有状态的正则表达式不再变化为止
    while True:
        new_regex = regex.copy()
        for s in dfa:
            for t, a in dfa[s].items():
                new_regex[t] = new_regex[t].replace(f'{a}', f'({a})')
                new_regex[t] = f'{new_regex[t]}|({new_regex[s]})({a})*'
        if new_regex == regex:
            break
        regex = new_regex

    # 输出每个状态的正则表达式
    for state in regex:
        print(f'{state}: {regex[state]}')

使用示例如下：

# 构造DFA
dfa = {
    0: {'a': 1, 'b': 2},
    1: {'a': 1, 'b': 3},
    2: {'a': 3, 'b': 2},
    3: {'a': 3, 'b': 3}
}

# 构造正规表达式
construct_regex(dfa)

输出结果为：

0: ((2)|(1))(a)*((3)|(2))(b)*
1: ((3)|(1))(a)*
2: ((2)|(3))(b)*
3: ((3)|(2))(a|(b))*

这就是使用图上作业法构造与DFA等价正规表达式的程序实现。