Exercise 1 Explain in English what the following FA accepts: Find the automata t

Question

Exercise 1 Explain in English what the following FA accepts: Find the automata that accept the following languages, -(0,1 -all strings with an odd number of l's -all strings with an even number of0's -all strings in which is 1 is the last symbol. -all strings which start with 0 and have the substring"11" where 00' is NOT a substring An even number of 1's and at least one 0 We present two FAs where the author of each FA has made an incorrect claim about the language it recognizes. For each FA, we list the file name where the FA is stored and the claimed language it recognizes. For each FA you must i) Produce six strings that are either in the indicated language but are not accepted by the FA, or that are accepted by the FA but not in the language ii) Simulate these strings on the FAs as well. ii) Modify the FA so that it actually recognizes the language we claim it does, iv) Simulate these strings again to show that the FA now rejects (resp. accepts) the strings it is supposed to. (a) The FA in ex1.6a recognizes the language of any string over the alphabet 2- (a,b) with exactly two b's (b) The FA in ex1.6c recognizes the language of any string over 2- (a,b,c) with at least 3 b's or at least 3 c's

Explanation / Answer

Excercise 1:

Path ABD with C is for two consective 0's

Path ACD with B is for two consective 1's

So any string which has either consecutive 1 or consecutive 0 then it will reach D

Once it is at D then it remains in D only.

Example:

01100110 -> accepted

010101001 -> accepted

010101 - > ends at state C therfore not accepted

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.