Q5. Do only parts b) and c). Exercise 6.2.1: Design a PDA to accept each of the following languages. You may accept either by final state or by empty stack, whichever is more convenient. * a) {0n 1n n ≥ 1}. We shall accept by empty stack. Symbol X will be used to count the 0's on the input. In state q, the start state, where we have seen no l's, we add an X to the stack for each 0 seen. The first X replaces Zo, the start symbol. When we see a 1, we go to state p, and then only pop the stack, one X for each input 1. Formally, the PDA is ({q, p}, {0,1}, {X, Zo}, 8, q, Zo). The rules: 8(q, 0, Zo) = {(q, X)} 8(q,0, X) = {(q, XX)} 8(q, 1, X) = {(p,ɛ)} 8(p, 1, X) = {(p,ɛ)} b) The set of all strings of 0's and 1 's such that no prefix has more l 's than 0's. c) The set of all strings of 0's and 1 's with a n equal number of 0's and I's.

Q5. Do only parts b) and c). Exercise 6.2.1: Design a PDA to accept each of the following languages. You may accept either by final state or by empty stack, whichever is more convenient. * a) {0n 1n n ≥ 1}. We shall accept by empty stack. Symbol X will be used to count the 0's on the input. In state q, the start state, where we have seen no l's, we add an X to the stack for each 0 seen. The first X replaces Zo, the start symbol. When we see a 1, we go to state p, and then only pop the stack, one X for each input 1. Formally, the PDA is ({q, p}, {0,1}, {X, Zo}, 8, q, Zo). The rules: 8(q, 0, Zo) = {(q, X)} 8(q,0, X) = {(q, XX)} 8(q, 1, X) = {(p,ɛ)} 8(p, 1, X) = {(p,ɛ)} b) The set of all strings of 0's and 1 's such that no prefix has more l 's than 0's. c) The set of all strings of 0's and 1 's with a n equal number of 0's and I's.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time. Your design (in pseudo code) should include a class Stack and three functions, i.e., push, pop, and min.
Please define and initialize and array X of length 8. You need implement following and write outcomes with reasons; 1.cout<< X+1; 2.cout<<&X+1; 3.cout<<2[X]; 4.cout<<&X[0]+1; 5.cout<<*(X+1); 6.cout<<*X+1; Also, practice and play with pointers using multiplication, division, subtraction and addition. You may also play with it your ways and find out reasoning. Write down those reasoning.
PYTHON: Please implement the stack algorithm (infix to postfix) in Python in such a way that the output will show the step-by-step solution or for the sake of clarity, the output should be like the given image. However, if it's too difficult for you to show the 'token' and 'operator stack' in the output, then at least the 'postfix string' must be present in the output. The program must get the infix expression from the user's input.
Please siiir solve thiss question, thaannks
a) Apply Bucket-Sort on the following input. Show your work in a similar way that we did in the class. Assume we use 10 buckets. A = [0.88, 0.32, 0.15, 0.6, 0.55, 0.11, 0.52, 0.12, 0.83, 0.31, 0.19, 0.81] b) We saw in the class that Bucket Sort is useful when the input is uniformly distributed. Consider the following input which is NOT uniformly sorted: n/logn items are uni- formly distributed in [0, 0.8], log² n items are uniformly distributed in (0.8, 0.9] and the remaining n - n/logn - log² n items are uniformly distributed in (0.9, 1]. Repeat the analysis from the class to describe the expected running time of Bucket- Sort with parameter k = n/20 for the above input. You may assume that we a comparison-based sorting algorithm with running time (n log n) to sort items within each bucket.
C4
Q6) Consider the infix expression exp = ( ( 8 / 2 ) + 3 ) * 1 to solve the questions given below: a: Trace the process of converting the infix expression into It's postfix form. b: Evaluate the postfix expression you obtained in part a. а: Content of stack Postfix expression Next token Action b: Next token Action Content of stack
Asapp
Q: * Present a DFA (deterministic finite automaton) that recognizes/accepts the language: L1 = { w ∈ {0,1}* | n0(w) ≡ 1 (mod 2) ∧ n1(w) ≠ 0 (mod 3) } In accord with Linz's notation, nc(x) is the number of occurrences of symbol c in string x. In words, L1 contains precisely those bit strings in which the number of occurrences of 0 is odd and the number of occurrences of 1 is not divisible by three.
Suppose that you want to create the following program: void copyStack(std::stack<int> &srcStack, std::stack<int> &dstStack); This operation copies the elements of srcStack in the same order onto dstStack. Consider the following statements: Int main() { Std::stack<int> stack1; Std::stack<int> stack2; … copyStack(stack1, stack2); The function copyStack(stack1, stack2); copies the elements of stack1 onto stack2 in the same order. That is, the top element of stack1 is the top element of stack2, and so on. The old contents of stack2 are destroyed and stack1 is unchanged. Note that std::stack<int> is a C++ standard library stack object type. Complete the following program void copyStack(std::stack<int> &srcStack, std::stack<int> &dstStack) { // check if srcStack is empty -> error message is printed and return // remove all the elements of dstStack // create a temporary stack tempStack for…
Construct a PDA for {a'b'|i # j}. State whether it is “accept by empty stack" or "accept by final state." Please also give a high-level description of your PDA. 7.
Modify the C++ class for the abstract stack type shown belowto use a linked list representation and test it with the same code thatappears in this chapter. #include <iostream.h>class Stack {private: //** These members are visible only to other//** members and friends (see Section 11.6.4)int *stackPtr;int maxLen;int topSub;public: //** These members are visible to clientsStack() { //** A constructorstackPtr = new int [100];maxLen = 99;topSub = -1;}~Stack() {delete [] stackPtr;}; //** A destructorvoid push(int number) {if (topSub == maxLen)cerr << "Error in push--stack is full\n";else stackPtr[++topSub] = number;}void pop() {if (empty())cerr << "Error in pop--stack is empty\n";else topSub--;}int top() {if (empty())cerr << "Error in top--stack is empty\n";elsereturn (stackPtr[topSub]);}int empty() {return (topSub == -1);} }