this project implement deterministic PDA to check if a string conforms to a grammar that generates statement blocks consisting of zero

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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

1. 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

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path 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 t

. 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 individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. 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

. 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