6 votes 6 votes Let $\mathrm{M}$ be a $8$-state Deterministic Finite Automaton over the alphabet $\{a, b, c\}$. If the language accepted by $\text{M}$ i.e. $\text{L(M)}$ is finite, then the maximum possible cardinality of $\text{L(M)}$ is __________. Theory of Computation goclasses2024-mockgate-13 goclasses numerical-answers theory-of-computation finite-automata 1-mark + – GO Classes asked Jan 28 • retagged Jan 28 by Lakshman Bhaiya GO Classes 621 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
6 votes 6 votes Detailed Video Solution: https://www.youtube.com/watch?v=kPLciwgwKaE GO Classes answered Jan 28 GO Classes comment Share Follow See 1 comment See all 1 1 comment reply Mahanth Yalla commented Jan 29 reply Follow Share As DFA, we should have all transitions for every state on every input {a,b,c} (keep an eye on the size of the input) so we should leave out the last state as the required is finite language (refer deepak sir's video: https://www.youtube.com/watch?v=kPLciwgwKaE) Maximum number of strings we can accept is given as $= 3^{0} +3^{1} +3^{2} +3^{3} +3^{4} +3^{5} +3^{6} $ $= \frac{3^{6+1} – 1 }{ 3 – 1 }$ $= \frac{ 2187 – 1 }{ 3 – 1 }$ $= \frac{ 2186 }{ 2}$ $= 1093 $ 10 votes 10 votes Please log in or register to add a comment.
