Recent questions tagged theory-of-computation

2 votes
1 answer
1861
If L is CFL then $\bar{L}$ is Recursive. ( True/False)If L is CFL then $\bar{L}$ is RE. (True/Flase).
0 votes
0 answers
1863
0 votes
0 answers
1864
Which one is True?$1)$ A set $S$ , some of it’s elements creates injective function. Then S is decidable$2)$ A bijective function can be $NP$ Hard$3)$ A function which...
0 votes
0 answers
1866
Match the following1.P2.NP3.NP-Complete4. NP-Hard1.Decidable2.Undecidable
0 votes
1 answer
1867
L= { M⟩|L(M) accepts empty string} L={⟨M⟩|TM halts on empty string} Identify RE , REC , Not RE ??Are this two languages or sameI think both are same if TM halts on...
0 votes
0 answers
1870
Consider the following PDA:The language accepted by the given PDA is: L = {(b^n a b^n a )^m | m, n >= 0} L = {b^n a b^n a | n >= 0} {bn | n >= 0} L = {b^n a b^n a | n >= ...
3 votes
1 answer
1871
in reversal of DFA if there are more than one final states then which one will be made the initial state? a DFA can have only one initial state
0 votes
1 answer
1872
0 votes
1 answer
1873
0 votes
0 answers
1874
Let $L_1= (0+1)^* , L_2=(01^*0 +1^*) \text{ and } L3=(01^+0 +1^+ + \epsilon) $.If $L=L_1 \cap L_2 \cap L_3$Then find the number of strings in $L$ which do not contain ...
0 votes
0 answers
1877
0 votes
0 answers
1878
Which of the following problem is undecidable?A) membership problem for CFLB) membership problem for regular languageC)membership problem for cslD)membership problem for ...
0 votes
3 answers
1880
Consider the following Finite State Automaton. The language accepted by the automaton is given by the regular expression.$ab^*b^*$$a^*b^*$$b^*b$$b^*ab^*$
2 votes
1 answer
1883
In the Given language $L=\{ab, aa, baaa\}$, ____ number of strings are in $L^*$baaabaaabaaaabaaabaaaabaabaaabaaa $1$$2$$3$$4$
0 votes
0 answers
1884
Why is Regular grammar obtained from DFA always unambiguous?Why Regular grammar obtained from NFA may or may not be ambiguous?
1 votes
0 answers
1885
Where can we apply PCP to check, if the grammar is undecidable?Some examples of such grammars Ambiguous grammarAny other example and how they solved with PCP?
0 votes
0 answers
1886
L={a$^{2*m}$ b$^{4*n}$ c$^{n}$ d$^{m}$ |m,n>=0}L={xwxw$^{r}$|x,w $\epsilon$ {0,1}} machine
0 votes
0 answers
1889
Is set difference operation is closed for two CFLs say L1 and L2? Please justify your answer.
0 votes
0 answers
1890