w Problem 5. [14 points) Consider the following setting. There are k processes that share a common resource (for example a printer). Let the symbols 1,8, -1,..., denote respectively the request by process i and the granting to process i of the resource. An execution is a string over the alphabet ? = {1,8...,8x). For example, the string 8g, indicates that first process 1 requests the resource, then process 2 requests it, then process 1 is granted the resource, and finally process 2 is granted it. Call an execution a,a, a, e incomplete if some process requests the resource in some step and is not granted it at any later step, i.e. if a, = r, for some , i and there does not exist a > such that a, -g; otherwise the execution is complete. For example, the executions 1817, 1728828, are incomplete, whereas 1788, 8,17282828, are complete (note that a grant to a process i satisfies all its previous requests). Let D, be the set of incomplete executions (strings). a. Give an NFA with k+1 states that accepts the language D. b. Give a DFA that accepts D. Justify your answers