Finding if there exists an input for a given automata for which no matter what the starting state is, final state would be same everytime
There's no need to define both __str__ and __repr__ for Node when they're both the same functionality. If you just define __repr__ it will be called in place of __str__ when necessary. (though the reverse is not true). See:

&gt;&gt;&gt; class A:
    def __repr__(self):
        return "self"

&gt;&gt;&gt; str(A())
'self'


Instead of assigning a value to x then deleting it with del, use pop.

x = y.pop(i)


This simultaneously passes y[i] to x while removing it from y.

x = y[i]


This is also quite a confusing function, adding a docstring would make it a lot clearer what it actually is/does. As would better names. y could be nodes_copy and x could be... node I guess? I'm not entirely clear on what x is meant to be for, since the name is meaningless. Also what's tNodes? Does the t stand for something? Traversed possibly? Except I don't see you adding anything to the empty list so I don't see what it does at all.

In FindTarget you're calculating node not in target twice. You do need to use this for two separate if statements, but you could just store the boolean to save running the test twice:

def FindTarget(node,p):
    if len(p) == 1:
        return node.dict[p[0]]

    node_in_target = node in target
    if not node_in_target or p not in target[node]:
        x = Gnodes[FindTarget(node,p[:-1])].dict[p[-1]]
        if not node_in_target:
            target[node] = {}
        target[node][p] = x
    return target[node][p]


As @JoeWallis pointed out, a dictionary is fast at testing these look ups, but that doesn't mean this wont still save time.

In allSatisy, isn't x just being set to the result of FindTarget(nodes[0], p)? Because FindTarget never returns None, x will always be set to some result and therefore will only be set on the first iteration. Unless I'm wrong and the node values returned from FindTarget can be None. If that's not the case though, this would make your function clearer:

def allSatisy(nodes,p):
    x = FindTarget(nodes[0], p)
    for node in nodes[1:]:
        if FindTarget(node,p) != x:
            return False
    return True


And if this is the same as your function, then there's a faster way to do this using Python's all function. It can take a generator expression to evaluate every element in a list for a condition and return the result as a single boolean. In your case, you want to know if all the results of FindTarget(node, p) are equal to x, for each node in nodes (after the first node). Thankfully that's practically the syntax:

def allSatisy(nodes,p):
    x = FindTarget(nodes[0], p)
    return all(FindTarget(node, p) == x for node in nodes[1:])