Hi, I need Help On a Autometa Theory Exam. This exam is on May 5th 2022, 7pm US central time. From the Time of uploading the pdf formatted exam the expert has 13 hours to complete the exam. The...

1 answer below »
Hi, I need Help On a Autometa Theory Exam. This exam is on May 5th 2022, 7pm US central time. From the Time of uploading the pdf formatted exam the expert has 13 hours to complete the exam. The solutions should be uploaded no later than 13 hours from the time if uploading the pdf file. There will be approximately7-9 questions (4-5 Multiplechoice). The questions in the exam will have 1 or 2 steps in between and the rest of the steps need to be filled in. I'M UPLOADING A SAMPLE EXAM., THIS IS ONLY TO SHOW THE FORMAT OF THE EXAM AND THE TYPE OF QUESTIONS. I WILL ALSO UPLOAD LECTURE NOTES. LECTURE NOTES ARE VERY IMPORTANT. USE STEPS IN LECTURE NOTES TO SOLVE QUESTIONS AND FINISH STEPS. VERY IMPORTANT TO GO OVER LECTURE NOTES, PLEASE DONOT ATTEMPT EXAM WITHOUT GOING OVER LECTURE NOTES.!!! DONOT COPY ANY SOLUTIONS FROM THE INTERNET I WANT UNIQUE SOLUTIONS.


CS 4384 Exam 2 April 7, 2022 • Submission deadline: 11:59PM, Friday, April 8, 2022. This deadline is strict. • Please do not communicate with your classmates during the exam period. Any violation of academic integrity will be reported to the UTD Office of Community Standards and Conduct. • Please print this document and write your solutions in the space provided for each question. Scan the document and submit it to eLearning. It is fine if you open the document on your tablet and write your answers. • Please make sure that your handwriting is legible. We will not grade any solution that is not readable or has scribbled parts. Name: Multiple choice questions No explanation is needed for any of the questions in this section. Please select the correct answer(s) only. 1. Let Σ = {a, b} be an alphabet and n ∈ N. What is the number of possible strings of length 2n over Σ? Choose the correct answer. (8 pt) (a) 2n! (b) n2n (c) 2nn (d) 22n 2. Which of the languages below is the described by the regular expression (0 + 1)∗1(0 + 1)∗1(1 + 0)∗? Choose the correct answer. (8 pt) (a) The set of all strings containing the substring 11. (b) The set of all strings containing at most two 1’s. (c) The set of all strings containing at least two 1’s. (d) The set of all strings that begin and end with either 0 or 1. 3. At least one of the following statements are correct. Choose the correct statement(s). (8 pt) (a) For every language L ⊆ Σ∗, ((∅ ∪∅) · L∗ = {ε}). (b) For every language L ⊆ Σ∗, (∅ · L∗ = {ε}). (c) For every language L ⊆ Σ∗, (∅ ∪ L+ = L∗) (d) For every language L ⊆ Σ∗, (({ε} ∩∅) · L∗ = {ε}). (e) For every language L ⊆ Σ∗, ({ε} ∪ L+ = L∗) Chandrahas Nanduri Chandrahas Nanduri Chandrahas Nanduri CS 4384 Exam 2 Page 2 of 6 4. Which of the grammmars below generates the language accepted by the following NFA? Choose the correct answer. (8 pt) (a) S → aSb | bSa | SS | ε (b) S → aS | bS | a | b (c) S → aS | bS | ε (d) S → aS | Sb | S | ε 5. Let L = {apbqar | q = p+r}. Which of the grammmars below generates L? Choose the correct answer. (8 pt) (a) S → BA A→ 0A1 | ε B → 1B0 | ε (b) S → AB A→ 0A1 | ε B → 1B0 | ε (c) S → ASBS A→ 01A | ε B → B10 | ε (d) S → ABC A→ 0A1 | ε B → 1B0 | ε C → a Cont. CS 4384 Exam 2 Page 3 of 6 Regular questions When answering questions in this section, you need to follow the given format. Fill in the empty sections that I provide below each question without skipping any of them. 6. The following languages are not regular. Complete the missing parts of their proofs of nonregularity. (15 pt) (a) L = {aibj | i = 2j}. i. Let n > 0. ii. Let z =?. Note that z ∈ L and |z| ≥ n. iii. Consider z = uvw such that |uv| ≤ n and |v| ≥ 1. iv. ? v. L is not regular. (b) L = {w ∈ {a, b, c}∗ | w is a palindrome (i.e. w = wR)}. i. Let n > 0. ii. Let z =?. Note that z ∈ L and |z| ≥ n iii. Consider z = uvw such that |uv| ≤ n and |v| ≥ 1. iv. ? v. L is not regular. Cont. CS 4384 Exam 2 Page 4 of 6 7. In this question, you will remove ε-productions from the following production grammar. (15 pt) S → aSb | bSa | SS | ε (Note: V = {S} and Σ = {a, b}) • Nullable symbols? • Eliminate nullable symbols? 8. In this question, you will design a CFG for the language L = {anbm | m ≥ n, m− n is even}. (15 pt) • Give the recursive definition? – Basis: ? – Recursive step: ? • List the rules of the CFG: ? Cont. CS 4384 Exam 2 Page 5 of 6 9. Convert each of the following regular expressions to equivalent NFAs. (15 pt) (a) (bab + aabaa)∗. Construct the NFA according to following steps. Do not skip any step. • NFA for a: • NFA for b: • NFA for bab: • NFA for aabaa: • NFA for (bab + aabaa): • NFA for (bab + aabaa)∗: Cont. CS 4384 Exam 2 Page 6 of 6 (b) (ba)∗ · (aab)∗. Construct the NFA according to following steps. Do not skip any step. • NFA for a: • NFA for b: • NFA for ba: • NFA for (ba)∗: • NFA for aab: • NFA for (aab)∗: • NFA for (ba)∗ · (aab)∗: The End.
Answered 2 days AfterMay 04, 2022

Answer To: Hi, I need Help On a Autometa Theory Exam. This exam is on May 5th 2022, 7pm US central time. From...

Parvesh answered on May 06 2022
89 Votes
CamScanner 05-06-2022 14.35.19
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here