Assignment 1 748 - واجب نظرية الحوسبة - Assignment 1

حل الواجب الأول لمقرر نظرية الحوسبة (Theory of Computation) للقسم 748، الفصل الدراسي الأول 2025-2026.

7 large KINGDOM OF SAUDI ARABIA | JAZAN UNIVERSITY COLLEGE OF ENGINEERING & COMPUTER SCIENCE ASSIGNMENT I - Academic Year Semester First Course with code Theory of Computation COMP) Section Type of Assignment Individual Marks 10 Date of Announcement Deadline ASSIGNMENT PROBLEM STATEMENT Answer All Questions. Each question carries TWO marks. 1. a) Convert the given NFA to DFA. (Show the steps) b) Write the regular expression for: Any no. of a followed by any no. of b followed by any no. of c. 2. Write the CNF for the given context-free grammar. S -> AAB A -> aAb | € B -> aB | a 3. Show that the language L={0^m 1^n 0^{m+n} | m>=1 and n>=1} is not regular using pumping lemma. 4. Check the ambiguity for the string ((0)) in the given grammar: S -> (A) | 0 A -> SB B -> SB | € 5. Convert the foll…