What are the correct answers for these questions involving regular languages and

Question

What are the correct answers for these questions involving regular languages and regular expression? Also, if you could provide a small explanation for each answer.

17. Consider the regular expr ession (a + b) (a +b) (a +b) (n-times). The minimum number of st ates in finite automaton that recognizes the language represented by this regular expression contains a. n states b. n1 states C. n2 states d. 2n states 18. The logic of pumping lemma is a good example of a. The pigeon hole principle b. Divide and conquer method c. teration d. Recursion 19. The basic limitation of a FSM is that a. It cannot remember arbitrary large amount of information b. It sometimes recognizes grammar that are not regular It sometimes fails to recognize grammars that are regular c. d. All of the above 20. Finite state machine recognize palindromes a. Can b. Cannot c. May d. May not 21. The graphical representation of the transition of finite automata is a. Finite diagram b. State diagram c. Node diagram d. E-R diagram 22. 'A language is regular if and only if it is accepted by a finite automation'? a. b. c. d. The given statement is true The given statement is false The given statement is partially true Sometime true, sometimes false 23. Write regular expression to denote a language L which accepts all the strings which begin or end with either 00 or 11

Explanation / Answer

Plase Note: According to Chegg Policy, you should post separate for Separate Questions. I have answered the first four. Please Re-Post Separate for the Separate Questions.

Answers)

Q17) Consider the regular expressions (a+b)(a+b)...(a+b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains :-

b. n+1 states - minimum number of states n+1 states will be required by the language represented by this regular expression.

Q18) The logic of pumping lemma is a good example of -

a. the pigeon hole principle - the pigeon – hole principle states if n pigeons fly in m holes, and n>m, then there must be 1 hole where there will be more than one pigeons.

Q19) The basic limitation of a FSM is that -

a. It cannot remember arbitrary large amount of information

Q20) Finite state machine ________ recognize palindromes.

b.cannot

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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