Due Date: Wednesday, April 16, 2025.

Purpose: This homework continues the work on formal grammar with more focus on regular grammars and finite state machines, based on the lectures in Module 11.

a. Write (as a comment in the Lisp file) a formal grammar converted from the following finite state machine:

b. Describe the language recognized by this grammar/FSM - what kind of strings can be generated with it?

c. Is this an NFA or a DFA? Justify the answer.

d. Write a Lisp program that verifies if a list of symbols is correct from the point of view of this grammar. For example,
(check-A '(y w z w y))   should return true (t) and
(check-A '(y z w w))       should return false (nil).

You can use the program grammar1.el as a model for this.

For this exercise, we will work on a regular grammar to recognize a comment in a C++ or Java program. A comment starts with /* and ends with */ and anything else in between can be ignored. We won't consider the case of nested comments. Keep in mind that you can have any number of * characters at the beginning, at the end, and in between.

• Write a regular grammar recognizing such comments.
• Draw the finite state machine for this grammar.
• Draw a table for this grammar such as the ones for table-driver scanners in the class notes and in the book.

Upload any files to Canvas, Assignments, Homework 11. You can write the non-coding parts on paper and scan them or take pictures of them to upload.