automata

Consider the following context-free grammar G, where S, A, and B are the variables (non-terminals), a and b are the terminal symbols, S is the start variable, and the rules of G ar...

A regular language L is accepted by a non-deterministic finite automaton (NFA) with n states. Which of the following statement(s) is/are FALSE?

Consider the following deterministic finite automaton (DFA) defined over the alphabet, $\Sigma = \{a, b\}$. Identify which of the following language(s) is/are accepted by the given...

Let Σ = {a, b, c}. For x ∈ Σ*, and α ∈ Σ, let #α(x) denote the number of occurrences of α in x. Which one or more of the following option(s) define(s) regular language(s)?

Let Σ = {1,2,3,4}. For x ∈ Σ*, let prod(x) be the product of symbols in x modulo 7. We take prod(ε) = 1, where ε is the null string. For example, prod(124) = (1 × 2 × 4) mod 7 = 1....

Consider the 5-state DFA M accepting the language L(M) ⊂ (0+1)* shown below. For any string w ∈ (0+1)* let n₀(w) be the number of 0's in w and n₁(w) be the number of 1's in w. Whic...

Let δ denote the transition function and $\hat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below: Then $\hat{\delta}(q_2,...

The number of states in the minimum sized $$DFA$$ that accepts the language defined by the regular expression $$${\left( {0 + 1} \right)^ * }\left( {0 + 1} \right){\left( {0 + 1} \...

Let $$L = \left\{ {w \in {{\left( {0 + 1} \right)}^ * }\left| {\,w} \right.} \right.$$ has even number of $$\,\left. {1's} \right\},$$ i.e $$L$$ is the set of all bit strings with...