3 votes 3 votes Consider the following non-deterministic finite automaton(NFA), where $\Sigma = \{a, b, c\}.$ How many strings of length $6$ are accepted by the given NFA over the alphabet $\Sigma=\{\mathrm{a}, \mathrm{b}, \mathrm{c}\}$ ? Theory of Computation goclasses2024-toc-2-weekly-quiz numerical-answers goclasses theory-of-computation finite-automata 2-marks + – GO Classes asked Jun 22, 2022 retagged Jun 17, 2023 by Lakshman Bhaiya GO Classes 538 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes The NFA recognizes the following language: $\text{L}_{1}=\{w$ : the second last symbol of $w$ is not ${'} a \text{'} \}$ GO Classes answered Jun 22, 2022 edited Jun 16, 2023 by Deepak Poonia GO Classes comment Share Follow See 1 comment See all 1 1 comment reply sk91 commented Jul 16, 2022 reply Follow Share Just to add to the above answer, First 4 characters can take anyone of {a,b,c} giving 3x3x3x3 = 81 possibilities The 5th character can have only two options {b,c} giving 81x2 = 162 possibilities Last character can take one of {a,b,c} giving 162x3 = 486 possible strings of length 6 Hence, answer is 486 14 votes 14 votes Please log in or register to add a comment.