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
- TBE103/03: Environmental Science and Design Report, WOU, Malaysia Green and sustainable development is globally promoted, and “Go Green” initiatives are also widely being encouraged in the country
- LAW416: Business Law Assignment, UiTM, Malaysia Lena a housewife, visits Tenggara Bhd, a company that sells various kinds of electrical goods for household purposes
- HFT20303: Financial Management Assignment, UMK, Malaysia How much money must be put into a bank account yielding 5% annually in order to have RM250 at the end of five years
- BBF201: Introduction To Financial Management Assignment, WOU, Malaysia In order to prepare to send his child to a medical school in the future, Encik Ishak wants to accumulate RM1.5 million
- BAIT2004: You are required to complete the tasks related to setting up local area networks and network configurations: Fundamentals of Computer Networks Assignment, TARC, Malaysia
- Kim, Kourtney, and Khloe are the shareholders of Dash Closets Sdn. Bhd. The authorised capital: Business Law Home Work, HU, Malaysia
- Advanced Strategic Management Case Study, ASB, Malaysia After many years that’s the Holy Grail that we’re finally starting to get traction on. We recognized in the 1990s that design
- Diploma in Network Technology Assignment, UCISS, Malaysia System Auto is a premier enterprise software company offering multiple products at scale both in the enterprise arena
- Managerial Finance Management and Investment Analysis Assignment Malaysia
- Bachelor of Information Technology Data Analytics Assignment, HU, Malaysia Describe the data set in the Introduction in terms of where this data set came from, what the data is about, and what you plan to do analyze
