Deterministic PDA implementation
Project Goal
The goal of this project is to implement a deterministic PDA to check if a string conforms to a grammar that generates statement blocks consisting of zero or more assignment statements followed by an arithmetic expression. The left side of an assignment statement is a variable name and the right side is an arithmetic expression. If it is valid, the PDA outputs the derivation starting from the start symbol else produce error if the string is not valid.
Grammar
It is a CFG grammar G = (V, Σ, P, S), where V = {S, B, T, T1, T2, F1, F2, X, C, N, I},
∑ = { a, b, c,…..z, A,B,C,……Z,0,1,2,…..9, +, -, *, /, (, ), =, ;, $} which
includes assignment operator = and statement separator symbol ;. The starting variable is S; and the rule set P is given as follows:
𝑺 → $𝑩$
𝑩 → 𝑻 | 𝑿 = 𝑻 ; 𝑩
𝑻 → 𝑻 + 𝑻𝟏 | 𝑻𝟏
𝑻𝟏 → 𝑻𝟏 − 𝑻𝟐 | 𝑻𝟐
𝑻𝟐 → 𝑻𝟐 ∗ 𝑭𝟏 | 𝑭𝟏
𝑭𝟏 → 𝑭𝟏 / 𝑭𝟐 | 𝑭𝟐
𝑭𝟐 → 𝑰 | 𝑿 | (𝑻)
𝑰 → 𝑵 𝑰 | 𝑵
𝑵 → 𝟎 | 𝟏 |𝟐 | 𝟑 |𝟒 |𝟓 |𝟔 |𝟕|𝟖|𝟗
𝑿 → 𝑪𝑿 | 𝑪
𝑪 → 𝒂 | 𝒃 |𝒄|… . 𝒛 |𝑨|𝑩|𝑪| … … |𝒁
Note that the variable symbols B,S,T,I,N,X and C are different from the terminal uppercase characters.
Leftmost derivation of the string “$a = 2; b = (a+5)*(a/2); fg = a-b; fg$” is given follows:
𝑺 → $𝑩$ → $𝑿 = 𝑻; 𝑩$ → $𝑪 = 𝑻; 𝑩$ → $𝒂 = 𝑻; 𝑩$ → $𝒂 = 𝑻𝟏; 𝑩$
→ $𝒂 = 𝑻𝟐; 𝑩$ → $𝒂 = 𝑭𝟏; 𝑩$ → $𝒂 = 𝑭𝟐; 𝑩$ → $𝒂 = 𝑰; 𝑩$
→ $𝒂 = 𝑵; 𝑩$ → $𝒂 = 𝟐; 𝑩$ → $𝒂 = 𝟐; 𝑿 = 𝑻; 𝑩$ → $𝒂 = 𝟐; 𝑪 = 𝑻; 𝑩$
→ $𝒂 = 𝟐; 𝒃 = 𝑻; 𝑩$ → $𝒂 = 𝟐; 𝒃 = 𝑻𝟏; 𝑩$ → $𝒂 = 𝟐; 𝒃 = 𝑻𝟐 ∗ 𝑭𝟏 ;
→ $𝒂 = 𝟐; 𝒃 = 𝑭𝟏 ∗ 𝑭𝟏; 𝑩$ → $𝒂 = 𝟐; 𝒃 = 𝑭𝟐 ∗ 𝑭𝟏; 𝑩$
→ $𝒂 = 𝟐; 𝒃 = (𝑻) ∗ 𝑭𝟏; 𝑩$ → $𝒂 = 𝟐; 𝒃 = (𝑻 + 𝑻𝟏) ∗ 𝑭𝟏; 𝑩$
→ $𝒂 = 𝟐; 𝒃 = (𝑻𝟏 + 𝑻𝟏) ∗ 𝑭𝟏; 𝑩$ → $𝒂 = 𝟐; 𝒃 = (𝑻𝟐 + 𝑭𝟏) ∗ 𝑭𝟏; 𝑩$
…….→ $𝒂 = 𝟐; 𝒃 = (𝒂 + 𝑭𝟏) ∗ 𝑭𝟏; 𝑩$ …. → $𝒂 = 𝟐; 𝒃 = (𝒂 + 𝟓) ∗ 𝑭𝟏; 𝑩$
→ $𝒂 = 𝟐; 𝒃 = (𝒂 + 𝟓) ∗ 𝑭𝟐; 𝑩$ → $𝒂 = 𝟐; 𝒃 = (𝒂 + 𝟓) ∗ (𝑻); 𝑩$
...→ $𝒂 = 𝟐; 𝒃 = (𝒂 + 𝟓) ∗ (a/2); 𝑩$ …→ $𝒂 = 𝟐; 𝒃 = (𝒂 + 𝟓) ∗ (a/2); X= T;
𝑩$ …. ...→ $𝒂 = 𝟐; 𝒃 = (𝒂 + 𝟓) ∗ (a/2); fg = a-b; B$
...→ $𝒂 = 𝟐; 𝒃 = (𝒂 + 𝟓) ∗ (a/2); fg = a-b; T$
......→ $𝒂 = 𝟐; 𝒃 = (𝒂 + 𝟓) ∗ (a/2); fg = a-b; fg$....
Rightmost derivation of the string “$a = 2; b = (a+5)*(a/2); fg = a-b; fg$” is given follows:
𝑺 → $𝑩$ → $𝑿 = 𝑻; 𝑩$ → $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑩$ → $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = 𝑻; 𝑩 $
→ $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = 𝑻; 𝑻𝟏$ → $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = 𝑻; 𝑻𝟏$ …
→ $𝑿 = 𝑻; 𝑿 = 𝑻; X = T;fg$ → $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = 𝑻𝟏; fg$
→ $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = 𝑻𝟏 − 𝑻𝟐; fg$ …→ $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = 𝑻𝟏 − 𝒃; fg$ .. →
$𝑿 = 𝑻; 𝑿 = 𝑻; 𝑿 = 𝒂 − 𝒃; fg$ → $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑪𝑿 = 𝒂 − 𝒃; fg$
→ $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑪𝑿 = 𝒂 − 𝒃; 𝐟𝐠$ → $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑪𝑪 = 𝒂 − 𝒃; fg$
→ $𝑿 = 𝑻; 𝑿 = 𝑻; 𝑪𝒈 = 𝒂 − 𝒃; fg$ → $𝑿 = 𝑻; 𝑿 = 𝑻 ; 𝒇𝒈 = 𝒂 − 𝒃; fg$ ….
→ $𝑿 = 𝑻; 𝐛 = (𝐚 + 𝟓) ∗ (𝐚/𝟐) ; 𝒇𝒈 = 𝒂 − 𝒃; fg$
….→ “$a = 2; b = (a+5)*(a/2); fg = a-b; fg
If you look at the reverse of the rightmost derivation, then we use reduction from left to right. For example after seeing “$a”, we first replace “a” by C which is again replaced by X to get $X. Then when we see “2”, we will replace it by I which is again replaced by X and then to T so we get $X=T based on what we have seen so far in the string. We keep adding input to $X=T until we reduce “b = (a+5)*(a/2)” by X=T so that we have $X=T; X=T reducing the string $a = 2; b = (a+5)*(a/2). Continuing this way we will reduce the string “$a = 2; b = (a+5)*(a/2); fg = a-b; fg” by $X=T; X=T; X=T;T. Reducing this we get $X=T; X=T; X=T;B which will be reduced to $X=T; X=T;B and so on until we get $B. When we see the final $, we will reduce $B$ by S. Parsers work this way by using shift-reduce actions; shift action involves pushing symbol from input string to stack and reduce action involves replacing the string from the top of the stack that
matches the right-hand side of a production rule by the non-terminal symbol on the left side of that rule. For example when the stack has “X = T; B” (first symbol is at top of the stack), reduce action can replace it by B using the production rule
𝑩 → 𝑿 = 𝑻 ; 𝑩
Deterministic PDA
Note that since the grammar is unambiguous you can define a deterministic PDA to recognize the language. There will be unique left-most and right-most derivations as mentioned before. Your first task is to design a deterministic PDA M= (Q,Σ,Γ,δ,q0,F) that recognizes strings that can be generated by the above grammar.
The PDA M must satisfy the following conditions:
The PDA must be defined with the alphabet Σ defined in equation (1). In other words the PDA must be able to handle any string of symbols from Σ. The PDA can handle certain strings not in A by crashing, i.e., the drawing does not have an edge leaving a state corresponding to particular symbols read and
The PDA must have exactly one accept
(c ) The states in the PDA must be labeled qo,q2,q3,...,qn-1, where q0 is the start state and n is the number of states in the PDA.
All edges in the PDA must correspond to reading a symbol from Σ; i.e., no edge can correspond to reading ε. There is no restriction on pushing or popping ε on
There is exactly one edge leaving the start state, and that arc has label “$, ε → $”. Thus, the first thing the PDA does is it reads a $ and pushes a $ on the
(f )Any edge going into the accept state has label “$, $ → ε”.
(g) There cannot be two edges corresponding to reading the same symbol a ∈ Σ and popping the same symbol b ∈ Γ leaving a single state.
You will not be able to use the construction specified in Lemma 2.21 to convert the CFG to a PDA as the resulting PDA will not satisfy the all the last four properties (d)-(g).
The drawing of your PDA must include all edges that are ever used in accepting a string in
But to simplify your drawing, those edges that will always lead to a string being rejected should be omitted. Specifically, when processing a string on your PDA, it might become clear at some point that the string will be rejected before reaching the end of the input. For example, if the input string is “$ab+*bc$”, then it is clear on reading the * that the string will
not be accepted. Moreover, if an input string ever contains the substring +*, then the input string will be rejected. Thus, your drawing should omit the transition corresponding to reading the * in this case, so the PDA drawing will crash at this point
60 Answers
90 Answers
DescriptionIn this final assignment, the students will demonstrate their ability to apply two majorconstructs of the C programming language – Functions and Arrays – to solve computationalproblems.Arrays provide a convenient way to store &
The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is anPath finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going through certain obstacles. As the main aim is to thinkabout path finding, we focus on the common task
Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individualDevelop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. TheLineItem class will represent an individual line item of merchandise that acustomer is purchasing.
SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define: SeaPortProgram e
Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define: SeaPortProgram e
The first programming project involves writing a program that parses, using recursive descent, a GUI definition language defined in an input file and generates the GUI that it defines. The grammar for this language is defined below:1Project 1The first programming project involves writing a program that parses, using recursive descent, a GUIdefinition language defined in an input file and generates the GUI that it defines. The grammar for thislanguage is defined below:gui ::= Wi
CMSC 335 Project SeaPort Solved Project 3 Introduction the SeaPort Project series For this set of projects for the course we wish to simulate some of the aspects of a number of Sea PortsCMSC 335 Project SolvedProject 3 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:
CMSC 335 Project 4 Solved SeaPort Introduction the SeaPort Project series For this set of projects for the course we wish to simulate some of the aspects of a number of Sea Ports Here are the classes and their instance variables we wish to defineProject 4 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define: SeaPortProgram ext
CMSC 451 Project 2 Solved The second project involves completing and extending the C++ program that evaluates statements of an expression language contained in the module 3 case studyProject 2 The second project involves completing and extending the C++ program that evaluates statements of an expression language contained in the module 3 case study. The statements of that expression language consist of an arithmetic expression f
CMSC 451 Project 1 Solved The first project involves benchmarking the behavior of Java implementations of one of the following sorting algorithms bubble sort selection sort insertion sort Shell sort, merge sort quick sort or heap sortCMSC 451 Project 1The first project involves benchmarking the behavior of Java implementations of one of thefollowing sorting algorithms, bubble sort, selection sort, insertion sort, Shell sort, merge sort,quick sort or heap sort. You must post your
The ready solutions purchased from Library are already used solutions. Please do not submit them directly as it may lead to plagiarism. Once paid, the solution file download link will be sent to your provided email. Please either use them for learning purpose or re-write them in your own language. In case if you haven't get the email, do let us know via chat support.
Get Free Quote!
270 Experts Online