rework

7

Computing Theory

COMPUTING THEORY

Q1: Learning Project of Deterministic Machine Simulation

This is the logical machine learning project where some deterministic machine simulation has to implement. For that JFLAP software is needed this is a java oriented software where this simulation can run. So for that we have to go to the Moore machine button where some node can be taken and then can logically connect the nodes as required. So as required answer need to take two variable as w1 and w2 and have to implement the whole logic with a, b, c, d nodes so for the first question take 6 nodes and name this nodes as a ,b ,c ,d and take the other node one as a space and another as a lambda. Then connect the nodes sequentially as connect the space node and the lambda node with the value space or as per question “B”.B is using as a space value to understand this properly. So then connect the B node and the‘d’ node with the value of ‘a’ (Cunningham et al. 2018, p.972). Then connect the‘d’ node and the ‘c’ node with the value of ‘b’. Then connect the ‘c’ node and the ‘b’ node with the value of ‘c’. Then connect the ‘b’ node and the ‘a’ node with the value of‘d’. Then connect the ‘a’ node with the both ‘B’ and‘d’ note so that loop can operate again. Then select the lambda node as a initial point then go to the input button and run all the simulation if “BabcdabcdB” will be the input then the output will be “BdcbadcbaB”

The structure of the body and the output will be like

Figure 1: Body Structure and the Output

(Source: FLAP software)

According to the second question we can implement this in two ways for the first technique 10 output have to be taken.8 nodes will connect with each other with the same value which is ‘a ‘and all nodes will be with the same name as ‘a ‘and rest of the two nodes is an initial node and the other will ‘B’ node. Last ‘a’ node will directly connect with the ‘B’ node so that when input will be gives as ‘BaaaaaaaaB’ the output will be ‘BaaaaaaaaB’. The body structure for the solution and the output will be like

Figure 2: Body Structure and the Output

(Source: JFLAP software)

The other one is the simplified way to solve the problem. So for that no need to take this number of nodes all is needed is 3 nodes one is the initial node another two is a ‘B’ node and an ‘a’ node. So connect the initial node with the ‘B’ node with the value of ‘B’ and the ‘B’ node will connect with the rest ‘a’ node with the value of ‘a’ and take the self loop on that ‘a’ node and connect with the ‘B’ node reversely (Oliva et al. 2018, p.64). So in this way the same output can come. The body structure and the output will be like

Figure 3: Body Structure and the Output

(Source: JFLAP software)

For the third question 12 node is needed one is the initial node and one is the ‘B’ node. So let's take the other node as required one ‘c’ node will be taken which is directly connect with the ‘B’ node with the value of ‘a’. In another side ‘c’ node connect with the ‘a’ node with the value of ‘b’ and ‘a’ node will connect with‘d’ node with the value of ‘c'. Let's make a self loop in‘d’ node with the value of ‘c’. Then connect the‘d’ node with the ‘c’ node with the value of‘d’. Then connect the ‘c’ node with ‘b’ node with the value of ‘a’. Then connect the ‘b’ node and the ‘a’ node with the value of ‘b’. Then connect the ‘a’ node and‘d’ node with the value of ‘c’. Then connect the‘d’ node and the ‘c’ node with the value of the‘d’. Again make a self node in ‘c’ node with the value of‘d’. Then take the ‘c’ node and connect with the ‘b’ node with the value of ‘a’. After that take the ‘b’ node and connect with the ‘a’ node with the value of ‘c’ and then connect the ‘a’ node with the ‘B’ node. After that if the input will be like ‘BabccdabcddacB’ so the output will be like ‘BcaddcbadccbaB’ so the body structure and the output will be like

Figure 3: Body Structure and the Output

(Source: JFLAP software)

Undesirability-

This is the part of the solvable solution so solvable solution is nothing but either knows there is some potential solution or an algorithm to find it or otherwise proved the problem cannot be solved. So undecidable is nothing but a solution which is only containing the procedure not algorithm and for this there is no Turing machine output will be there (Mohammed , Shaffer, Rodger, 2018, p.8).

this determining problem of containing Turing machine of two tape where never writes the blank symbol in its tape, where N = { M , wi | M where M is the tape Turing machine where writes a non blank symbol on its tape when this will be runs on w. So that will be show N is undecidable. Such as Use a reduction from Atm for that lets take N is as decidable and D which will be a decider for N = accept if M running on w writes a non-blank on its second tape reject if M running on w so this will not write a non-blank on its second tape. Use D to define a tm .On input hM, where M is an arbitrary one-tape Turing machine and w ∈ Σ ∗ , (1) Create TM M0 that will differs from the M only in being a two-tape Turing machine that doesn't use the second tape except for that one case. If M will accept the input, it writes a non-blank symbol on the second tape (Pereira & Terra, 2018, p.76). This was done by a simple change of the transition function. the transition function which is δ of M maps the accept state of M for a tape symbol to the empty set , the transition function δ 0 of M0 writes the non-blank on the second tape. If D = accept and if D = reject. That means H = (accept if M will accept and w reject if M will not accept W So, H will decided that Atm which is a undecidable. So it can say that N cannot be a decidable value.

Complexity

Complexity is the part of the computer theory which helps to solve the complexity problem which is used in Turing machine. An algorithm also comes with the complexity. Complexity classes can be used in a group or together problems which require similar amounts of resources. For example, problems which easily can solved in the polynomial time which is considered as a part of the class P. The group of problems which is takes an exponential amount of the space in the class EXPSPACE. Some of the classes are contained other classes .If a problem that can be solved in polynomial time then this can be solved in exponential time as well.

Reference List

Cunningham, C., Mokuvos, J., Li, M., Zhou, S., & Liu, S. (2019). Automated Exercises.

Mohammed, M., Shaffer, C. A., & Rodger, S. H. (2019, February). Using Interactive Visualization and Programmed Instruction to Teach Formal Languages. In Proceedings of the 50th ACM Technical Symposium on Computer Science Education (pp. 1263-1263). ACM.

Oliva, E. S., Diaz Ogas, M., Molina, A. L., & Alonso, N. (2019, June). Abordaje de expresiones regulares y sus derivadas mediante la utilización del software JFLAP. In XXI Workshop de Investigadores en Ciencias de la Computación (WICC 2019, Universidad Nacional de San Juan)..

Pereira, C. H., & Terra, R. (2018). A mobile app for teaching formal languages and automata. Computer Applications in Engineering Education, 26(5), 1742-1752.