Suppose the PDA P = (Q= {go, q1}, Σ={0,1}, r={Zo, X}, &, qo, z=Zo, F={q1} ) has the following transition function: Automata theory, Assignment, UMS, Malaysia
| University | Universiti Malaysia Sarawak (UMS) |
| Subject | Automata theory |
1. Suppose the PDA P = (Q= {go, q1}, Σ={0,1}, r={Zo, X}, &, qo, z=Zo, F={q1} ) has the following transition function:
a. (go, 0, Zo) = {(go, XZo)}.
b. (go, 0, X)= {(go, XX)}.
c. (go, 1, X)= {(go, X)}.
d. (qo, λ, X)= {(1, 2)}.
e. &(q1, λ, X)= {(91, λ)}. f. &(q1, 1, X)= {(91, XX)}. g. (q1, 1, Zo) = {(1, 2)}.
Starting from the initial ID (go, w, Zo), show ALL the reachable ID’s and list the transition functions that are used when the input w is:
a. 01. [Hint: there are two ways]
b. 0011. [Hint: there are three ways] c. 010.
(6 marks) (19 marks) (5 marks)
5. Let C be a context-free language and R be a regular language. Let P be the PDA that recognizes C, and D be the DFA that recognizes R. If Q is the set of states of P and Q’ is the set of states of D, we can construct a PDA P’ that recognizes CR with the set of states Q x Q’. P’ will do what P does and also keep track of the states of D. It will accept a string wiff it stops a a state qe FpxFD, where Fp is the set of accept states of P and FD is the set of accept states of D. Since CR is recognized by P’, it is context free.
Let A= {w we (a, b, c)* and w contains equal numbers of a’s, b’s, and c’s}. Use the fact that CR is context free to show that A is not a context free language.
Get Help By Expert
Recent Solved Questions
- Students are tasked with designing a health or safety education activity for children: Health and Safety for young children, Report, OUM, Malaysia
- MH370: Crisis Communication Management Strategies Assignment, MMA, Malaysia All businesses in the world are vulnerable to crises that can give a damaging impact on the organization’s reputation
- Guidance and Counselling Assignment: School-Based Mental Health and Therapeutic Resistance Case Study in Malaysia
- BBF201/03: INTRODUCTION TO FINANCIAL MANAGEMENT Assignment, WOU, Malaysia You are a manager who work at finance department of AVILLION BERHAD in Malaysia. You are interested to analyse the core principles of finance
- Accounting Assignment, UTM, Malaysia Mr. Arif received his monthly bank statement for the month ended 31 March 2022 on 15 April 2022
- Occupational Safety and Health Management Report, OUM, malaysia Discuss the tragedy happened in this movie from the point of view of the Domino Theory and Multiple Causation Theory
- Introduction to Fintech Assignment, APU, Malaysia Revolute is a British financial technology company that offers banking services Headquartered in London
- Big Data and Ethics Essay, APU, Malaysia The U.S. firm Apple operates a digital ecosystem with its own hardware and software. Part of this ecosystem is an app store
- MAT1106: Business Mathematics Assignment, IIU, Malaysia A company makes (window) frames and doors. It makes a profit of $30 on frames and $35 on a door
- Financial Assignment, TARC, Malaysia I know much money must be put into a bank account yielding 5% annually in order to have RM 250 at the end of five years
