- Published: September 10, 2022
- Updated: September 10, 2022
- University / College: University of Houston
- Level: Undergraduate
- Language: English
- Downloads: 38
Math Problem, Mathematics MATH203 – Applications Discrete Mathematics -PHASE 4 DB Q1: Transition Diagram Drawing of a transition diagram(digraph)
Q 2: The 5 strings generated by the automation are as follows:
String 1 = v = x + y
String 2 = x = x + δ
String 3 = w where (w = uv, the substring of w)
String 4 = s4 = w + x
String 5 = s5 = w + δ
Q 3: 5 Strings that use similar inputs but not in same language
String 1 = v = x + δ
String 2 = x = x + δ
String 3 = w = xδ
String 4 = s4 = δx
String 5 = δ + δ + x
Question 4: Statement describing the conditions of a string
When a string is part of the Language
When a string is in the accept mode, the input string is generated. The automation is able to read in the string one symbol each time from left to the right (McCulloch & Pitts, 1943). The automation begins to calculate immediately as the start state begins and it continues to read the initial symbol of the input string (Rabin & Scott, 1959). It also follows this state transition related to the initial symbol. The automation proceeds to read the symbols as it follows the transitions. This only ends when all the symbols have been read from the input. The computation ends at this point. If the automation remains in the accept state after processing every input symbol, then the string was accepted as part of that language (Lawson, 2004).
When a string is not part of the Language
On the other hand, Hopcroft, Motwani and Ullman (2001) and Sakarovitch (2009) explain that if the automation does not remain in the accept state after processing the symbols, it is not accepted and is not part of this language.
References
Hopcroft, J. E, Motwani, R. & Ullman, J. D. (2001). Introduction to Automata Theory, Languages, and Computation (2 ed.). Addison Wesley.
Lawson, M. V. (2004). Finite automata. Chapman and Hall/CRC.
McCulloch, W. S., Pitts, E. (1943). ” A logical calculus of the ideas imminent in nervous activity”. Bulletin of Mathematical Biophysics: 541–544.
Rabin, M. O., Scott, D. (1959). ” Finite automata and their decision problems.” IBM J. Res. Develop.: 114–125.
Sakarovitch, J. (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press.
