edited by
223 views
0 votes
0 votes

Which of the following problems are decidable?

  1. Checking whether two regular languages are equivalent
  2. Checking whether two non-deterministic finite automata accept the same language 
  3. Checking whether two context free grammars generate equivalent languages
  4. Checking whether a language of a  context free grammar is non-empty
  1. $\text{I, II}$ and $\text{IV}$ only
  2. $\text{I, II}$ and $\text{III}$ only
  3. $\text{I, II, III}$ and $\text{IV}$
  4. $\text{I}$ and $\text{II}$ only
edited by

1 Answer

Answer:

Related questions

0 votes
0 votes
0 answers
1
admin asked Jan 5, 2019
258 views
The problem of finding an integral solution of a given system of integral polynomial equations has complexity:Polynomial-timeExponential-spaceUndecidableExponential-time
0 votes
0 votes
1 answer
2
admin asked Jan 5, 2019
244 views
Which of the following languages over the alphabet $\Sigma = \{0,1\}$ is regular?$0^{n} 1^{m}$$0^{n} 1^{m}$ where $m=n+1$$0^{m} 1^{n}$ where $m \equiv n(\text{mod 3}).$ $...
1 votes
1 votes
1 answer
4
admin asked Jan 5, 2019
380 views
The set of equations $x^{2} + y^{2} = 1$ and $x + y = 0$ has how many real solutions?Infinite number of solutionsNo solution$2$ solutions$1$ solution