Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Webpage for Theory of Computation:
Recent questions tagged theory-of-computation
2
votes
1
answer
1861
Self Doubt
If L is CFL then $\bar{L}$ is Recursive. ( True/False) If L is CFL then $\bar{L}$ is RE. (True/Flase).
If L is CFL then $\bar{L}$ is Recursive. ( True/False)If L is CFL then $\bar{L}$ is RE. (True/Flase).
kumar.dilip
459
views
kumar.dilip
asked
Dec 13, 2018
Theory of Computation
theory-of-computation
decidability
+
–
4
votes
3
answers
1862
Regular language
L={a^m b^n | m-n=even} Is this language a regular language?
L={a^m b^n | m-n=even} Is this language a regular language?
AIkiran01
3.8k
views
AIkiran01
asked
Dec 12, 2018
Theory of Computation
theory-of-computation
finite-automata
regular-language
regular-expression
identify-class-language
+
–
0
votes
0
answers
1863
Draw PDA for this
L = { a^m b^n c^k=m+n } Please draw PDA for this Language!
L = { a^m b^n c^k=m+n } Please draw PDA for this Language!
Guilherme Zanini Mor
526
views
Guilherme Zanini Mor
asked
Dec 12, 2018
Theory of Computation
theory-of-computation
pushdown-automata
dpda
+
–
0
votes
0
answers
1864
Decidable
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 is Recursive Enumerable. Inverse of this function is decidable
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...
srestha
385
views
srestha
asked
Dec 12, 2018
Theory of Computation
theory-of-computation
decidability
+
–
0
votes
0
answers
1865
Draw PDA for this
L = {a^m b^n c^k=m+n } | m >= 0 and n >= 0 ---------------------- Please draw PDA for this Language!
L = {a^m b^n c^k=m+n } | m >= 0 and n >= 0 Please draw PDA for this Language!
Guilherme Zanini Mor
521
views
Guilherme Zanini Mor
asked
Dec 12, 2018
Theory of Computation
theory-of-computation
pushdown-automata
context-free-language
dcfl
+
–
0
votes
0
answers
1866
Decidability
Match the following 1.P 2.NP 3.NP-Complete 4. NP-Hard 1.Decidable 2.Undecidable
Match the following1.P2.NP3.NP-Complete4. NP-Hard1.Decidable2.Undecidable
srestha
319
views
srestha
asked
Dec 12, 2018
Theory of Computation
theory-of-computation
+
–
0
votes
1
answer
1867
Self Doubt
L= { M⟩|L(M) accepts empty string} L={⟨M⟩|TM halts on empty string} Identify RE , REC , Not RE ?? Are this two languages or same I think both are same if TM halts on $\epsilon$ then L(M) accepts $\epsilon$ right ??
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...
jatin khachane 1
384
views
jatin khachane 1
asked
Dec 10, 2018
Theory of Computation
theory-of-computation
decidability
+
–
1
votes
3
answers
1868
Halting problem of TM which recognize recursive languages is undecidable?
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
gmrishikumar
1.7k
views
gmrishikumar
asked
Dec 10, 2018
Theory of Computation
decidability
recursive-and-recursively-enumerable-languages
theory-of-computation
turing-machine
rice-theorem
+
–
0
votes
0
answers
1869
MadeEasy Subject Test 2019: Theory Of Computation - Pushdown Automata
Options: $\left \{ \left ( b^{n}ab^{n}a\right )^{m} | n,m \geq 0 \right \}$ $\left \{ \left ( b^{n}ab^{n}a\right )^{m} | n,m \geq 0 \right \} \cup \left \{ b^{n} | n\geq 0 \right \}$ $\left \{ \left ( b^{n}ab^{n}\right )^{m}a | n,m \geq 0 \right \}$ $NONE$
Options:$\left \{ \left ( b^{n}ab^{n}a\right )^{m} | n,m \geq 0 \right \}$$\left \{ \left ( b^{n}ab^{n}a\right )^{m} | n,m \geq 0 \right \} \cup \left \{ b^{n} | n\geq 0 ...
jatin khachane 1
871
views
jatin khachane 1
asked
Dec 10, 2018
Theory of Computation
made-easy-test-series
theory-of-computation
pushdown-automata
+
–
0
votes
0
answers
1870
pda doubt
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 >= 0} L = {(b^n a b^n a )^m | m, n >= 0} {bn | n >= 0}
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 >= ...
Satbir
428
views
Satbir
asked
Dec 10, 2018
Theory of Computation
pushdown-automata
theory-of-computation
+
–
3
votes
1
answer
1871
Reversal of DFA doubt
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
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
aditi19
2.3k
views
aditi19
asked
Dec 10, 2018
Theory of Computation
theory-of-computation
finite-automata
minimal-state-automata
+
–
0
votes
1
answer
1872
ME Test Series
Shadan Karim
168
views
Shadan Karim
asked
Dec 10, 2018
Theory of Computation
theory-of-computation
+
–
0
votes
1
answer
1873
Self Doubt
Equal Or Not $\Sigma ^{+} = L . L^{*} ?$
Equal Or Not$\Sigma ^{+} = L . L^{*} ?$
jatin khachane 1
322
views
jatin khachane 1
asked
Dec 10, 2018
Theory of Computation
theory-of-computation
+
–
0
votes
0
answers
1874
THEORY OF COMPUTATION
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 $11$.
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 ...
ROHIT SHARMA 5
272
views
ROHIT SHARMA 5
asked
Dec 10, 2018
Theory of Computation
theory-of-computation
regular-language
+
–
0
votes
0
answers
1875
proving a language is regular based on two regular language over same $\Sigma$ (complicated)
Hello, I've encountered with a difficult question i don't know how to solve. the question is about proving that a language is regular based on two language over the same $\Sigma$. the questions goes ... know it's complicated and would appreciate help with it. thank you very much your much appreciated help!
Hello,I’ve encountered with a difficult question i don’t know how to solve. the question is about proving that a language is regular based on two language over the sa...
csenoob
204
views
csenoob
asked
Dec 8, 2018
Theory of Computation
regular-language
theory-of-computation
finite-automata
closure-property
+
–
0
votes
0
answers
1876
VirtualGate CFL or Regular language Identification
For $\text{A, B} \subseteq \Sigma^*,$ define $A/B = \{x \in \Sigma^* | \exists y \in B , xy \in A \}$ If L is a CFL and R is regular, then L/R is Regular CFL but not regular Recursive but not CFL None of the above ... are not regular but they are CFL. Hence, $L/R$ is CFL but not Regular. Please advise me that am I thinking in correct way or not?
For $\text{A, B} \subseteq \Sigma^*,$ define$A/B = \{x \in \Sigma^* | \exists y \in B , xy \in A \}$If L is a CFL and R is regular, then L/R isRegularCFL but not regula...
!KARAN
395
views
!KARAN
asked
Dec 8, 2018
Theory of Computation
theory-of-computation
identify-class-language
+
–
0
votes
0
answers
1877
PDA toc
Plz tell me answer of the below question In automaton theory ,a PDA is a variation of: 1)finite automaton that can make use of a stack containing data 2)infinite automaton that can make use of a stack containing data 3)both A and B 4)none of the above
Plz tell me answer of the below questionIn automaton theory ,a PDA is a variation of:1)finite automaton that can make use of a stack containing data2)infinite automaton t...
Shivshankar
586
views
Shivshankar
asked
Dec 8, 2018
Theory of Computation
theory-of-computation
pushdown-automata
+
–
0
votes
0
answers
1878
Grammer
Which of the following problem is undecidable? A) membership problem for CFL B) membership problem for regular language C)membership problem for csl D)membership problem for type O language
Which of the following problem is undecidable?A) membership problem for CFLB) membership problem for regular languageC)membership problem for cslD)membership problem for ...
Shivshankar
496
views
Shivshankar
asked
Dec 8, 2018
Theory of Computation
theory-of-computation
grammar
+
–
0
votes
0
answers
1879
finding equivalence classes $R_L$ of given languages and separating words
hello, i've just solved 2 questions among many, but i'm not sure i've got to the right result. could you check if i did it correctly(especially 2) as it's more complicated). both are over ... classes. could you help me with that please? thank you very much for your help, really hoping i did it correctly.
hello,i’ve just solved 2 questions among many, but i’m not sure i’ve got to the right result. could you check if i did it correctly(especially 2) as it’s more com...
csenoob
366
views
csenoob
asked
Dec 7, 2018
Theory of Computation
finite-automata
equivalence-class
myhill-nerode
theory-of-computation
+
–
0
votes
3
answers
1880
NIELIT 2018-40
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^*$
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^*$
Arjun
905
views
Arjun
asked
Dec 7, 2018
Theory of Computation
nielit-2018
theory-of-computation
finite-automata
+
–
0
votes
1
answer
1881
NIELIT 2018-43
Which of the following languages over the alphabet $[0,1]$ is described by the given regular expression: $(0+1)^*1(0+1)^*1$? The set of all strings containing the substring $11$ The set of all strings containing at most two $1$’s The set of all strings containing at least two $1$’s The set of all strings that begins and ends with only $0$
Which of the following languages over the alphabet $[0,1]$ is described by the given regular expression: $(0+1)^*1(0+1)^*1$?The set of all strings containing the substrin...
Arjun
3.6k
views
Arjun
asked
Dec 7, 2018
Theory of Computation
nielit-2018
theory-of-computation
regular-expression
+
–
0
votes
3
answers
1882
NIELIT 2018-81
Identify the true statement from the given statements: A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language. The complement of a recursive languages is recursive The complement of a context-free language is context-free Only $1$ $1$ and $2$ $1$, $2$ and $3$ $2$ and $3$
Identify the true statement from the given statements:A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language...
Arjun
1.4k
views
Arjun
asked
Dec 7, 2018
Theory of Computation
nielit-2018
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
2
votes
1
answer
1883
NIELIT 2018-83
In the Given language $L=\{ab, aa, baaa\}$, ____ number of strings are in $L^*$ baaaba aabaaaa baaabaaaabaa baaabaaa $1$ $2$ $3$ $4$
In the Given language $L=\{ab, aa, baaa\}$, ____ number of strings are in $L^*$baaabaaabaaaabaaabaaaabaabaaabaaa $1$$2$$3$$4$
Arjun
1.1k
views
Arjun
asked
Dec 7, 2018
Theory of Computation
nielit-2018
theory-of-computation
regular-language
+
–
0
votes
0
answers
1884
DFA NFA and ambiguity
Why is Regular grammar obtained from DFA always unambiguous? Why Regular grammar obtained from NFA may or may not be ambiguous?
Why is Regular grammar obtained from DFA always unambiguous?Why Regular grammar obtained from NFA may or may not be ambiguous?
OneZero
577
views
OneZero
asked
Dec 7, 2018
Theory of Computation
theory-of-computation
finite-automata
ambiguous
+
–
1
votes
0
answers
1885
Undecidability with PCP
Where can we apply PCP to check, if the grammar is undecidable? Some examples of such grammars Ambiguous grammar Any other example and how they solved with PCP?
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?
srestha
367
views
srestha
asked
Dec 6, 2018
Theory of Computation
theory-of-computation
decidability
+
–
0
votes
0
answers
1886
toc nie
L={a$^{2*m}$ b$^{4*n}$ c$^{n}$ d$^{m}$ |m,n>=0} L={xwxw$^{r}$|x,w $\epsilon$ {0,1}} machine
L={a$^{2*m}$ b$^{4*n}$ c$^{n}$ d$^{m}$ |m,n>=0}L={xwxw$^{r}$|x,w $\epsilon$ {0,1}} machine
amit166
610
views
amit166
asked
Dec 5, 2018
Theory of Computation
theory-of-computation
+
–
0
votes
0
answers
1887
going from equivalnce classes into a DFA
Hello all, I saw an interesting question and i was wondering how to solve it. basically the subject i am having trouble with is going from equivalence classes of $R_L$ to building a DFA. The question: L is a language over {0,1}, for which ... how do you go from equivalence classes to finding the DFA? don't understand it. thank you very much for your help
Hello all,I saw an interesting question and i was wondering how to solve it. basically the subject i am having trouble with is going from equivalence classes of $R_L$ to ...
csenoob
443
views
csenoob
asked
Dec 5, 2018
Theory of Computation
finite-automata
theory-of-computation
compiler-design
regular-language
+
–
0
votes
0
answers
1888
Self doubt
One general doubt for minimum number of states in DFA. As explained here https://gateoverflow.in/2144/gate2011-42 If they are asking for minimum states in FA then we will consider min{dfs's, nfa's states} and include dead state in dfa but as we can see in ... we have not considered any dead state. Is it because it will lead to non final state itself? is that a reason or anything else?
One general doubt for minimum number of states in DFA. As explained here https://gateoverflow.in/2144/gate2011-42 If they are asking for minimum states in FA then we will...
S Ram
240
views
S Ram
asked
Dec 5, 2018
Theory of Computation
theory-of-computation
+
–
0
votes
0
answers
1889
Self Doubt
Is set difference operation is closed for two CFLs say L1 and L2? Please justify your answer.
Is set difference operation is closed for two CFLs say L1 and L2? Please justify your answer.
S Ram
196
views
S Ram
asked
Dec 4, 2018
Theory of Computation
theory-of-computation
+
–
0
votes
0
answers
1890
NIELIT Qtn
Consider the following possible outcomes of executing a Turing machine over a given input. Which of the following outcome is NOT possible? A)TM halts and accepts the input B)TM halts and rejects the input C)TM hangs and accepts the input D)TM never halts.
Consider the following possible outcomes of executing a Turing machine over a given input. Which of the following outcome is NOT possible?A)TM halts and accepts the input...
pps121
254
views
pps121
asked
Dec 2, 2018
Theory of Computation
turing-machine
theory-of-computation
+
–
Page:
« prev
1
...
58
59
60
61
62
63
64
65
66
67
68
...
155
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register