Register

#Self doubt

• edited by
173 views
0 votes
0 votes
1) Why equality problem of CFG is undecidable?

2) Why  emptiness problem of turing machine  is undecidable?
• edited by
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

122
views
1 answers
0 votes
Dknights asked Jan 8
122 views
#self doubt
a^n ww^r a^n .. (n>=0, w belongs to (a,b)*)Can someone please explain the flow how we will process the language in CFL.
User Avatar
238
views
2 answers
0 votes
Dknights asked Dec 23, 2023
238 views
#self doubt
MIN DFA of {w: w contains an even number of 0s and exactly two 1s} MIN DFA of {w: w contains an even number of 0s or exactly two 1s} ex 111 is valid
User Avatar
708
views
1 answers
0 votes
Sunnidhya Roy asked Dec 12, 2022
708 views
#Self Doubt
L = {0^n 1^2n 0^n+m , n,m>=0}Is this Language CFL or non CFL?According to mewe can write this as 0^n 1^n 1^n 0^n 0^mThen we will keep on ... and when we reach the end of the string we simply move to the final state.Is this logic correct?
User Avatar
417
views
0 answers
2 votes
Sunnidhya Roy asked Dec 11, 2022
417 views
#Self Doubt
Suppose L1 = CFL and L2 = Regular, We are to find out whether L1 - L2 = CFL or non CFL.I have 2 approaches to this question and I am confused ... Language is also CFL so CFL intersection CFL = non CFL.Can somebody please clarify my doubt?
User Avatar
Link Copied!