代做Algorithm | assignment – Computer Science 3050H Winter 2023 ass2

2024-06-03

Computer Science 3050H Winter 2023 ass2

代做Algorithm | assignment – 这个题目属于一个Algorithm的代写任务, 是比较典型的Algorithm等代写方向, 这是值得参考的assignment代写的题目

算法代写 代写算法 Algorithm代写 代写Algorithm 算法作业代写

Computer Science 3050H
Winter 2023
 assignment 2

  1. Consider the following two languages over the alphabet = {a, b}: L 1 is the language of all words with an odd number of a s and L 2 is the language of all words that begins with the substring ba. a) Using the trial and effort method we demonstrated in lecture, draw FA 1 : a machine that L 1 and FA 2 : a machine that accepts L 2. b) Using the Algorithm providing by Kleenes Theorem, construct the FA machine that accepts L 1 + L 2.

  2. Draw a Moore Machine to count the occurrences of the substrings bab or aba in words over the alphabet S={a ,b}. As discussed in Module 2, Finite Automata with Output, simply output a 1 at the end position of the desired substrings from the input string. For example, the input string abaababa would output 000100011.

  3. Convert the following Moore Machine into a Mealy Machine.

  4. Convert the following Mealy Machine into a Moore Machine.

  5. Consider the following languages over the alphabet S={a ,b}: L 1 is the language of all words that end with the substring ab while L 2 is the language of all words with an odd number of letters. Draw finite automata for L 1 and L 2 and using one of the two algorithms we discussed in Module 3, Regular Languages, construct the finite automata that accepts L 1 L 2.

  1. Are the languages accepted by the following FAs equivalent? Using the algorithm discussed in Module 3, Decidability Problems to prove your answer (show all the intermediate steps).

  2. Use the pumping lemma to prove the following language is nonregular: L = {a^2 nbn} = {aab, aaaabb, aaaaaabbb, …}

  3. Find CFGs that for these regular languages over the alphabet = {a, b}. Draw a Finite Automata first and use this to create the CFG. (a) The language of all words that does not contain any double letters ( aa or bb ). (b) The set of all words that begin with the letter a and contains an odd number of a s or begin with the letter b and contains an even number of b s.