908 views
2 votes
2 votes

 Consider a DFA with 1000000000000000000000000000 states, over the input alphabet consisting of all Greek alphabet letters. What can we say about it?

a.It is not possible that it accepts the empty set.

b.It is not possible that it accepts only empty string.

c.It is not possible that it accepts strings of length 1 only.

d.It is possible that it accepts all strings over the input alphabet.

2 Answers

1 votes
1 votes
Note: empty set means nothing accepted and empty string means only epsilon accepted.

a. false since if dfa doesn't having  final state it can accept empty set.

b. false since if only initial state is final and there is no inward transitions for initial state.

c.false we can draw a dfa which can accept strings of length one.

d. true if all states are final.
0 votes
0 votes
It is possible that it accepts all strings over the input alphabet

Related questions

0 votes
0 votes
1 answer
1
M_Umair_Khan42900 asked Dec 29, 2022
754 views
Show that the following pairs of regular expressions define the same language over the alphabet I = [a, b].s(a) p(pp)*( A + p)q + q and p*q(b) A +0(0+1)* + (0+1)* 00(0+1)...
0 votes
0 votes
0 answers
2
sripo asked Oct 10, 2018
652 views
For $\sum$={a,b} Re given is b*ab*(aa)*b* this is non minimized dfa but when the dfa is minimized we get RE as b*a(a+b)*. How to show that are they equivalent or is it ju...
0 votes
0 votes
1 answer
3
goluabhinan asked Sep 11, 2018
785 views
Consider the regular expression R = a*b* + b*a*. The number of equivalence classes of Σ* to represent a language which is equivalent to R is ____________.
0 votes
0 votes
2 answers
4