Run candidate elimination on three ⟨sky,temp,humidity⟩ examples (two positive, one negative) and print the final S-boundary and G-boundary.

Answer

def more_general(h1, h2): for a, b in zip(h1, h2): if a != '?' and a != b: return False return True def consistent(h, x): for hi, xi in zip(h, x): if hi != '?' and hi != xi: return False return True def candidate_elim(values, examples): n = len(examples[0][0]) S = [tuple(['0'] * n)] # most specific: covers nothing G = [tuple(['?'] * n)] # most general: covers everything for x, pos in examples: if pos: G = [g for g in G if consistent(g, x)] newS = [] for s in S: if consistent(s, x): newS.append(s) else: g = list(s) for i in range(n): if s[i] == '0': g[i] = x[i] elif s[i] != x[i]: g[i] = '?' newS.append(tuple(g)) S = [s for s in newS if any(more_general(g, s) for g in G)] else: S = [s for s in S if not consistent(s, x)] newG = [] for g in G: if not consistent(g, x): newG.append(g) else: for i in range(n): if g[i] == '?': for v in values[i]: if v != x[i]: c = list(g); c[i] = v; c = tuple(c) if any(more_general(c, s) for s in S): newG.append(c) G = [g for g in newG if not any(g != h and more_general(h, g) for h in newG)] return S, G def fmt(h): return '<' + ','.join(h) + '>' values = [['sunny', 'rainy'], ['warm', 'cold'], ['high', 'low']] examples = [ (('sunny', 'warm', 'high'), True), (('sunny', 'warm', 'low'), True), (('rainy', 'cold', 'high'), False), ] S, G = candidate_elim(values, examples) print('S = [' + ', '.join(fmt(h) for h in sorted(S)) + ']') print('G = [' + ', '.join(fmt(h) for h in sorted(G)) + ']')