Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers

1.6k comments

529 users

0 votes

While the model solution is alright. I solved this a bit differently where,

Q1 --a--> Q0 (instead of self loop)
Q4 --a--> Q3 (instead of self loop)

Would this be correct? Or is such backtracking not allowed as we are trying to create deterministic automata?

EDIT:

Q0: {s0}{}, Q1: {s0,s1}{}, Q3:{s2}{s2}, Q4: {s2,s3}{s2,s3}, Q2:sink state

in * TF "Emb. Sys. and Rob." by (610 points)
edited by
What is S1, S0, S3 and S4. Can you show your automaton?
Updated the question.

1 Answer

0 votes

In general, I do not recommend such "optimizations" since they quickly lead to mistakes. Automata store something about the previous input sequence in the states, and maybe you destroy that invariant with your "optimizations". Your suggestions turn out to be incorrect, I tried them with a tool, in that I called the original states q0,q1,q2,q3,q4 and the new ones of your automaton p0,p1,p2,p3,p4 and then stated that ((F G (q3|q4)) <-> F G(p3|p4)) holds. I got then the following counterexample:

-> State: 1.1 <-
  a = TRUE
  q0 = TRUE
  q1 = FALSE
  q2 = FALSE
  q3 = FALSE
  q4 = FALSE
  p0 = TRUE
  p1 = FALSE
  p2 = FALSE
  p3 = FALSE
  p4 = FALSE
-> State: 1.2 <-
  a = FALSE
  q0 = FALSE
  q1 = TRUE
  p0 = FALSE
  p1 = TRUE
-> State: 1.3 <-
  a = TRUE
  q1 = FALSE
  q3 = TRUE
  p1 = FALSE
  p3 = TRUE
-> State: 1.4 <-
  a = FALSE
  q3 = FALSE
  q4 = TRUE
  p3 = FALSE
  p4 = TRUE
-> State: 1.5 <-
  a = TRUE
  q3 = TRUE
  q4 = FALSE
  p3 = TRUE
  p4 = FALSE
-> State: 1.6 <-
  q3 = FALSE
  q4 = TRUE
  p3 = FALSE
  p4 = TRUE
-> State: 1.7 <-
  a = FALSE
  p3 = TRUE
  p4 = FALSE
-> State: 1.8 <-
  a = TRUE
  q3 = TRUE
  q4 = FALSE
  p2 = TRUE
  p3 = FALSE
-- Loop starts here
-> State: 1.9 <-
  a = FALSE
  q3 = FALSE
  q4 = TRUE
-> State: 1.10 <-
  a = TRUE
  q3 = TRUE
  q4 = FALSE
-> State: 1.11 <-
  a = FALSE
  q3 = FALSE
  q4 = TRUE

by (166k points)
Got the point!. Thank you.

Related questions

0 votes
1 answer
+7 votes
1 answer
0 votes
1 answer
0 votes
1 answer
asked Jun 13, 2023 in * TF "Emb. Sys. and Rob." by farwinr (380 points)
Imprint | Privacy Policy
...