(a) Design a PDA P that recognizes the language L = {r#y : x, y E{1}* ^ |r| > ly|} over the alphabet E = {1, #}. Draw a statediagram according to the format of the textbook and the slides,i.e., start with an empty stack. Furthermore, ensure that everymove either pushes or pops, but not both.(b) Obviously, you can casily create a CFG for such a trivial languagelike L. Here, you are asked to not just produce any CFG for L,but follow the procedure PDA-to-CFG to obtain such a grammar.Even for such a simple PDA, the grammar would be a bit lengthy.Therefore, we make one modification. You don't have to writeany rules that involve variables that generate the empty language.Such rules would have no effect anyway.

Answered: Image /qna-images/answer/e6f03382-ece6-4f68-9bb6-72060466e63a.jpg

a) Design a PDA P that recognizes the language L = {r#y : 1,Y E {1}* ^ \r| > ]y]} over the alphabet E = {1, #}. Draw a state diagram according to the format of the textbook and the slides, i.c., start with an empty stack. Furthermore, ensure that every move cither pushes or pops, but not both.

a) Design a PDA P that recognizes the language L = {r#y : 1,Y E {1}* ^ \r| > ]y]} over the alphabet E = {1, #}. Draw a state diagram according to the format of the textbook and the slides, i.c., start with an empty stack. Furthermore, ensure that every move cither pushes or pops, but not both.

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter18: Stacks And Queues

Section: Chapter Questions

Problem 16PE: The implementation of a queue in an array, as given in this chapter, uses the variable count to...

See similar textbooks

Similar questions

Your task for this assignment is to identify a spanning tree in a connected undirected weighted graph using C++. 1. Implement a spanning tree algorithm using C++. A spanning tree is an acyclic spanning subgraph of the of a connected undirected weighted graph. Your program will be interactive. Graph edges with respective weights (i.e., v1 v2 w) are entered at the command line and results are displayed on the console. 2. Each input transaction represents an undirected edge of a connected weighted graph. The edge consists of two unequal uppercase letters representing graph vertices that the edge connects. Each edge has an assigned weight. The edge weight is a positive integer in the range 1 to 99. The three values on each input transaction are separated by a single space. An input transaction containing the string “end-of-file” signals the end of the graph edge input. After the edge information is read, the spanning tree evaluation process begins. Use an adjacency matrix for recording…
Develop a program in C++ that will implement a Josephus Circle using circular linked list. There are n people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number m which indicates that m-1 persons are skipped and mth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive.
Develop a program in C++ that will implement a Josephus Circle using circular linked list. There are n people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number m which indicates that m-1 persons are skipped and mth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive. ***Using #include <iostream>
Write a c++ code that compare the times to traverse a list (containing a large number of elements) implemented in an array, in a simple linked list, and in an unrolled linked list. In this experiment, you need to generate a large list, store it in each representation, and then measure the time to traverse the list in each representation. For the array, this is almost straightforward: Fill the array and then do a sequential scan. Here is the thing to watch for: When you fill the array, it all gets read into cache. So, somehow you need to ensure that almost all of the array is NOT in cache before you do your traversal. One thing you can do is make your array big enough that most of it will not fit in cache at once. You need to make sure that the node capacity is not too small, or it will behave too much like a simple linked list.
IN C++ The input to the problem is a collection of n points in the plane. The points have int values.The goal of the traveling salesperson problem is to find the shortest path that visits every point exactly once and returns to the starting point. That is, we are looking for a cycle in the graph that visits each vertex exactly once, such that the total length is as small as possible. Storing the points:You will need to write a class that stores a collection of points. You may use any data structure you want to do it (array, linked list or vector in C++) Print the list of points:Your solution should have a method that prints the list of all points. Your solution should have a method that draws the points on the screen. You will need to implement a heuristic algorithm that finds a solution to the TSP problem
Consider the data structure stack's implementation. If we make an integer stack, the push and pop actions will only work with integer items. When we construct a character stack, the push and pop operations will only handle components of the character type. However, making so many copies of the implementation makes the code difficult to maintain. As a result, the genericity principle is applied, and a template class may be constructed. At runtime, this container class can handle any data type element. Explain the significance of modeling in object oriented programming using the same comparison.
Design and implement an application that reads a sentence fromthe user and prints the sentence with the characters of each wordbackwards. Use a stack to reverse the characters of each word.PP 12.3 Modify the solution to the postfix expression evaluation problemso that it checks for the validity of the expression that is enteredby the user. Issue an appropriate error message when an erroneous situation is encountered.
Please follow and understand the graph to code. Use DFS!
Your task for this assignment is to identify a spanning tree in one connected undirectedweighted graph using C++.1. Implement a spanning tree algorithm using C++. A spanning tree is an acyclic spanningsubgraph of the of a connected undirected weighted graph. The program is interactive.Graph edges with respective weights (i.e., v1 v2 w) are entered at the command line andresults are displayed on the console.2. Each input transaction represents an undirected edge of a connected weighted graph. Theedge consists of two unequal non-negative integers in the range 0 to 9 representing graphvertices that the edge connects. Each edge has an assigned weight. The edge weight is apositive integer in the range 1 to 99. The three integers on each input transaction areseparated by space. An input transaction containing the string “end-of-file” signalsthe endof the graph edge input. After the edge information is read, the process begins. Use anadjacency matrix for recording input edges and show all…
2. Implement a Reference-Based ADT Stack and verify "isEmpty()", "push()", "pop()", "popAll()", and "peak()" operations.
Consider a (literal) plate stack. If the stack becomes too tall, it may collapse.In practise, we would most likely create a new stack when the preceding stack reaches a certain threshold. Create a data structure SetOfStacks that is similar to this. SetOfStacks should be made up of many stacks and should build a new stack when the preceding one reaches its capacity.SetOfStacks. Push() and SetOfStacks are both functions. pop() should operate exactly like a single stack (that is, it should return the same values as if there were just one stack).COMPLETE THE FORMULACreate a popAt(int index) method that executes a pop operation on a given substack.
Use a stack implementation, to check that a given an arithmetic expression, that uses braces “{“ & ”}” or parenthesis ”(“ &, ”)” or brackets ”[“ & ”]” as grouping symbols, is using them in a matching and balanced way. Hint: The book has an example function, called isBalance( ), that takes the input string as an argument and returns 0 if it is unbalanced or 1 if it is balanced.(Examples below are given only for illustrative purposes, you may come up with your own.)