Complete 3 exercises related to theoretical aspects of computer science

Consider the following NFA over the alphabet Σ = {0, 1} A B C 0 1 0 1 (8 marks) a) Use the GNFA algorithm to get the equivalent regular expression for this NFA. (12 marks) b) Use the subset construction method to the equivalent DFA for this NFA. Specify it in the form of a transition table and a state diagram. ➋ a) Let Σ = {0, 1} and L be given by the regular expression 0(10)∗ + 1(01)∗ (12 marks) . Design an NFA to recognize L. Start with the following incomplete state diagram: S A10 B10 A01 B01 (8 marks) b) Design a grammar for L using only three variables: S, A, B. ➌ Consider the following PDA over Σ = {0, 1} and Γ = {0, 1, •} A B C D L R ε, ε → • 0, ε → 0 1, ε → 1 ε, ε → ε 0, ε → ε ε, • → ε 0, ε → ε 0, 0 → ε 1, 1 → ε (6 marks) a) Give 3 strings that are accepted by this PDA, and another 3 strings which are rejected by it. (4 marks) b) What is the general form of the strings accepted by this PDA?