how CTL formulas are interpreted on a graph Python using pyEDA package,Let G be a graph over 32 nodes.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

cpts515 Midterm Exam

Do in Python using pyEDA  package . You may find installation instructions at https://pyeda.readthedocs.io/en/latest/install.html

Understand how CTL formulas are interpreted on a graph.

1. 0.Let G be a graph over 32 nodes (namely, node 0, · , node 31). For all

0 ≤ i,j   ≤31, there is an edge from node i to node j  if·f (i + 3)%32 = j%32

or (i + 8)%32 = j%32. (% is the modular operator in C; e.g., 35% 32=3.) A node i is even if i is an even number. A node i is prime if i is a prime number.

In particular, we define [even] as the set  {0 , 2  , 4 ·,6·…· .30}     and [prime]

as the set { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31} . We use R to denote the set of all edges in G.

1. (20%, graded on correctness and efficiency) (write-up) Let p be a CTL formula while [p] is the set of nodes in G that satisfy p.
   • Please design afix-point iteration algorithm that computes [EFp] (the set of nodes in G that satisfy EF p from R and [p]).
   • Please design afix-point iteration algorithm thatcomputes [EGp](theset of nodes in G that satisfy EGp from R and [p]).

You may first study the algorithms for [AGp] and [AF p].

2. (50%, graded on correctness and If you use explicit graph search such as DFS, you receive 0.) (coding in Python) Every finite set can be coded as a BDD. Please write a Python program to compute [EG(even∧ EFprime)] (the set of nodes that satisfy the formula EG( even∧ EF prime).), and verify

your answer by checking

node 5 satisfies EG(even∧ EF prime) and node 6 doesn’t satisfy EG(even∧ EF prime).

(Important: your code shall first encode R, [even], [prime] in BDDs using pyEDA and then using methods provided with the package, implement the iteration algorithms provided in 3 symbolically in BDD using methods in the package. Many students’ find methods BDD. compose () and BDD. smoothing () are quite useful in the package.)

3. (30%, graded on originality, depth, and quality of ) (write-up) To make use of the idea of BDDs, a major difficulty is which graph is chosen to model a given set of data. When the graph is too large, the symbolic exploartion algorithm would not even run efficiently. However, if the graph is too small, the modeling might not be even realistic. We now think about an example problem. Consider a finite set L of DNA strands, where each strand is simply a string on alphabet {A, T, C, G} (that is, a strand is a sequence of nucleotides, each of which is chosen from four nitrogen-containing nucleobases.). One  may use a  deterministic  finite  automaton (DFA)1  M

(which itself is a graph) to model the set L; i.e  L  ⊆    L(M ). That is, each

strand w in L, there is a walk in M (from the initial state to an accepting state) such that the symbols sequentially collected on the transitions on the walk form exactly the w. Clearly, many many different M can be used to model L (e.g., M can be ridiculously simple with only one state and accepting every word on the alphabet.). Consequently, one need come up with a metric Q(M, L), which is a real number, to characterize the “precision” on using the given M to model L. When this is done, one can argue, for two given DFAs M1  and M2  which both model the given L, which model is more precise. Now, you need write a mini-paper (of 1 or 2 or more pages) in figuring out ways to define Q(M, L) and to design algorithms to compute Q(M, L).23

1I assume that you know finite automata theory, which is covered in wsu undergaduate required course cpts317.

2Important: I am not interested in how to create a model M from the given L. Instead, I am interested in, when M and L are given, how to measure the precision.

3More important: L(M ) or the language accepted by the given model M is most likely to be an infinite language. But the given set L is always finite. The case that L(M ) is finite is trivial and don’t spend a minute on it.

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