The smallest finite automaton, which accepts the language { x | length of x is divisible by 3} has

Which of the following statements true?

Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.

The C language is

Consider a DFA over $\sum$= {a,b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?

Consider the following languages:

Which of these languages is/are regular?

Which of the following is true?

The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as

The problems 3-SAT and 2-SAT are

Consider the two statements: S1 : {0²ⁿ |n $\ge$ 1| } is a regular language S2 : {0^m1ⁿ 0^m+n | m $\ge$ 1 and n $\ge$ 1| } is a regular language

Which of the following statements is incorrect?

pts all those binary strings in which the number of 1's and 0's are respectively

Consider the following problem x:

Given a Turing machine M over the input alphabet ^$\sum$, any state q of M. A word w ^{$\in\sum^*$} does the computation of M on w visit the state q.

Which of the following statements about x is correct?

The language {a^mb^m+n | m,n $\le$ 1} is

Consider the flowing grammar C S $\rightarrow$ bS |aA| b A$\rightarrow$ bA | aB B bB |aS| a Let N_a (W) and N_b (W) denote the number of a's and b's in a string W respectively. The language L(G) {a,b}+ generated by G is

L₁ is a recursively enumerable language over$\sum$. An algorithm A effectively enumerates its words as w₁,w₂,w₃,.... Define another language L₂ over $\sum \cup$ {#} as {w_i # wj: w_i, w_j $\in$ L₁, i < j}. Here # is a new symbol. Consider the following assertion. S₁:L₁ is recursive implies L₂ is recursive S₂:L₂ is recursive implies L₁ is recursive

Which of the following statements is true?

Let L₁ be a recursive language, and let L₂ be a recursively enumerable but not a recursive language. Which one of the following is true?

Consider the machine M

The language recognized by M is

Let Nf and Np denote the classes of languages accepted by nondeterministic finite automata and non-deterministic push-down automata, respectively. let Df and DP denote the classes of languages accepted by deterministic finite automata and deterministic push down automata, respectively. Which one of the following is true?

Consider three decision problems P₁, P₂ and P₃. It is known that P₁ is decidable and P₂ is undecidable. Which of the following statements is true?

Consider the languages L₁ {aⁿ bⁿ c^m | n, m > 0} and L₂ {aⁿ b^m c^m | n, m > 0}

Consider the following languages:

L₁ = {WW^R | W^_$\in$ {0, 1}} L₂ = {W # W^R |W^_$\in$ {0, 1}} where # is a special symbol L₃ = {WW | W^_$\in$ {0, 1}*}

Which of the following statements is true?

Consider the following two problems on undirected graphs ^_$\alpha$: Given G(V,E), does G have an independent set of size |V |− 4? ^_$\beta$: Given G(V,E), does G have an independent set of size 5?

Which one of the following is true?