Let w be any string of length n in \{0, 1\}^*. Let L be the set of all

Back to the 2019 paper

Module 1: Introduction, Regular languages and finite automata

20192m

Let $w$ be any string of length $n$ in $\{0, 1\}^*$ . Let $L$ be the set of all substrings of $w$ . What is the minimum number of states in a non-deterministic FA that accepts $L$ ?

(i) $n - 1$
(ii) $n$
(iii) $n + 1$
(iv) $2n - 1$

Search Google Ask AI

Similar questions

Formal Language & Automata TheoryA minimum state deterministic FA accepting the language L = \{w \mid w \in \{0, 1\}^*\} where number of 0's and 1's in w are divisible by 3 and 5 respectively, has (i) 15 states (ii) 11 states (iii) 10 states (iv) 9 states20212m FORMAL LANGUAGE & AUTOMATA THEORYA minimum state deterministic FA accepting the language: L = \{ w \mid w \in \{0,1\}^* \} where the number of 0's and 1's in w are divisible by 3 and 5 respectively, has: (i) 15 states (ii) 11 states (iii) 10 states (iv) 9 states20232m Formal Language & Automata TheoryConsider the regular expression (0+1)(0+1)\dots N \text{ times}. The minimum state FA that recognizes the language represented by this regular expression contains (i) n states (ii) (n+1) states (iii) (n+2) states (iv) None of the above20192m Formal Language & Automata TheoryWhat is the minimum number of states in deterministic finite automata (DFA) for string starting with ba^2 and ending with a over alphabet \{a, b\}? (i) Ten (ii) Nine (iii) Eight (iv) Six20202m

PreviousConsider the grammar G whose SLR parser has n_1 states and LALR parser has n_2 states. What is the relation between n_1 and n_2? (i) n_1 = n_2 (ii) n_1 < n_2 (iii) n_1 > n_2 (iv) None of the above NextConsider the regular expression (0+1)(0+1)\dots N \text{ times}. The minimum state FA that recognizes the language represented by this regular expression contains (i) n states (ii) (n+1) states (iii) (n+2) states (iv) None of the above