Select all the statements below which are true: If a language L can be represent

Question

Select all the statements below which are true: If a language L can be represented by a nfa, then we can also compute a dfa for L. The transition function of a dfa cannot be defined using a transition table. O Let {al, aa» . . , an} Let M be a dfa and let GM be the corresponding transition graph. Let m be the number of vertices in GM. Then m 2n. Let M be a nfa. The language L accepted by M consists of all the strings w for which there exists a walk labeled w from the initial state to some final state. Let M be a na. If the initial state qo is also a final state, then e L (M) O Let = {0, 1,2} and go be the initial state of a na M. Then the transition graph of M has a maximum of 3 outgoing edges at go If a language L can be represented by a dfa or by a nfa, then L is regular.

Explanation / Answer

1) If a language L can be represented by a NFA, then we can also compute a DFA for L

Ans) This statement is True, Because every NFA can be converted into equivalent DFA. And also DFA, NFA and Regualar Expressions are all equivalent. We can construct DFA from NFA using subset construnction. Therefore, every NFA is DFA and vice versa.

2) The transistion function of DFA can not be defined using Transistion table

Ans) This is False statement. Because every trasistion function can be defined using table

3) The third statement which is m>=n

And)Third statement is false. Because for example if we take the language sigma* , which is all the words. It can be drawn using single vertex. Here m is less than n. Therefore it is a false statement

4)Let m be a NFA. The language L accepted by M consists of all the strings w for which there exists a walk lableled w from the initial state to some final state.

Ans) This statement is True. We say the language accepted by nfa is the set of strings that are accepted by the NFA. So there must be an walk labeled w from the initial state to some final state which is the accepting state.

5)Let M be a Nfa. If the inital state q0 is also final state, then lambda belongs L(M)

Ans) Lambda means an empty string. So the statement is true. Because the given nfa can accept the empty string. Therefore lambda belongs to the given language

6) Ans) True. Because there are 3 different types of transistions that can take by qo. One is q0 on reading 0,1,2 it can go to 3 different states. So it has 3outgoing edges. And the minimum number is 1

7)If a language L can be represented by a dfa or by a nfa, then L is regular

Ans) This statement is true. Because All finite languages are regular but not vice versa.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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