True or False

Question 1

A function f is a morphism if f (xy) = f (y)f (x) holds for all x, y ∈ dom(f ).

Answer 1

False

Question 2

Each subset of a semigroup that is closed under the binary operation of the semigroup is a semigroup

Answer 2

True

Question 3

Each surjective semigroup homomorphism is an endomorphism.

Answer 3

False. epimorphism
injective => monomorphism
isomorphism => bijective
S=T => endomorphism
isomorphism and endomorphism => automorphism

Question 4

A group is called simple if {e} and G are the only normal subgroups

Answer 4

True

Question 5

A group is called simple if and only if {e} and G are the only subgroups

Answer 5

False

Question 6

The direct product of semigroups is commutative

Answer 6

False

Question 7

The operation on the direct product of semi-groups is defined component wise

Answer 7

True

Question 8

In state machines, the transition function is total.

Answer 8

False. In deterministic finite automata (DFA) + Turing Machine ==> total. In nondeterministic finite automata (NFA), Mealy or Moore machine might not be total

Question 9

A cyclic state machine with stern of length r and cycle of length p has (r + p) many states

Answer 9

True

Question 10

Two words u, v are equivalent w.r.t. a state machine M if no matter in which state we start to read them, we end in the same state

Answer 10

True

Question 11

The semigroup of a state machine is the set of nonempty words factorized by the equivalence relation w.r.t. the state machine

Answer 11

True

Question 12

One of the action conditions is ∀q ∈ Q: qs1 = qs2 ⇒ s1 = s2.

Answer 12

False

Question 13

The semigroup of a state machine is the semigroup of the associated transformation semigroup

Answer 13

True

Question 14

For group G, (G, G) is the transformation group of G.

Answer 14

True

Question 15

A state machine homomorphism is a function f such that f(qq’)=f(q)f(q’) for all q belongs to Q and q’ belongs to Q’

Answer 15

False

Question 16

TS(SM(A)) ≅ A for a transformation semigroup A

Answer 16

True

Question 17

Since admissible partitions of a set of states Q belong to a state machine, the do not define an equivalence relation on Q

Answer 17

False. admissible partitions of a set of states Q do define an equivalence relation on Q

Question 18

Quotient state machines w.r.t. a partition π have the π-blocks as states

Answer 18

True

Question 19

The function η of a covering needs to be total

Answer 19

False. the function η in a covering does not have to be a total function.

Question 20

Each state machine is covered by its state machine constructed by coinciding inputs.

Answer 20

True

Question 21

An orbit of a group is a left coset.

Answer 21

True

Question 22

A state machine consists of a well-defined set of initial states.

Answer 22

False

Question 23

A state machine is complete iff the transition relation is a function.

Answer 23

True

Question 24

A state machine is completable by introducing a sink.

Answer 24

True

Question 25

The semigroup of a state machine M consists of all the equivalence
classes of ~M

Answer 25

True

Question 26

For all state machines M, S(M) is a monoid.

Answer 26

False

Question 27

Each transformation semigroup is a semigroup

Answer 27

False

Question 28

Each transformation semigroup is associated with a state machine

Answer 28

False

Question 29

A state machine homomorphism is a tuple of two homomorphisms.

Answer 29

True

Question 30

Each state machine homomorphism can be transformed into a homomorphism of the associated transformation semigroups.

Answer 30

False

Question 31

SM(TS(A)) ≅ M for all state machines M

Answer 31

False

Question 32

A covering of state machines is an injective function between the alphabets.

Answer 32

False