This is CORRECT. The language reduces to L = {wxw | x and w are any string over the alphabet} You can prove that the language is non-regular using the pumping lemma for regular languages.

29 Oct 2017 - 7:22pm

@dashish @shraddhagami : Oh yeah, so basically that still works. Even if \(w \in \Sigma^+\), you would simply need to ensure that the beginning and ending letter is the same, which an FA (Finite Automaton) can remember to do.

23 Jan 2017 - 11:44pm

Dear @shraddhagami, understand that the key trick here is that the language is \(w~x~w^r\) and \(wx\) cannot be the empty string. Every non-empty string starts and ends with the empty string. Do you agree with this? If you do, then you will see, that for the empty string \((w = \epsilon)\) is equivalent to  \((w^r = \epsilon)\). Therefore, any string between the epsilon can be matched to the pattern \(x\) and therefore, the language if studied is actually going to be the language  \(L = \Sigma^+\)

23 Jan 2017 - 8:35pm

I do not believe any of these options is correct. In both cases, observe that for automaton Y and Z on a (b) from the start state (1) they both go to the final state (2). Therefore in the product this will happen too. Using just this, we see that the only possible option is option (A) in which state (P) on a (b) goes to state (R), the final state. However (P) on an (a) goes to (S) , whereas (S) on an (a) should go back to (P) which doesn't happen. So the only feasible answer seems incorrect too.

20 Jan 2017 - 12:42pm

Every regular expression determines a set of strings. Hence we have the following equivalences.

b* = {\(\epsilon\), b, bb, bbb, ...}
a = {a}
\(\epsilon\) = {\(\epsilon\)}
a + b* = {\(\epsilon\), a, b, bb, bbb, ...}
ε + a+b* = {\(\epsilon\), a, b, bb, bbb, ...} = (a+b*)
Now, if R is a regular expression, R+ is any string in R repeated (by concatenation) once or more.


(ε + a+b*) includes ε repeated once or more, which is ε. Therefore (ε + a+b*)+= (a+b*)+ =(a+b)*

18 Sep 2016 - 1:54am

A language that is decidable is both Turing Recognizable and Co-Turing Recognizable (Its complement is Turing Recognizable). (i) is false, and hence (D) is incorrect.

15 Sep 2016 - 5:37pm

@hradeshpatel: As @koushiksinha has responded, perhaps I can further explain.

In language A, any string w in the language is of the form xy, however the choice of "where to split w to get parts x and y" is what is called a non-deterministic choice. Hence, given any word w, so long as there is some way of breaking w into x and y such that it fits into the criteria of belongingness to A, it can be thought of a being in A. What makes A regular? Now that's an interesting notion. Think about what the language A will actually be. The language A will contain all strings in {a,b}*. Why so? Because for any string in the set (a+b)*, the string can always be broken into an x and y such the number of a's in x is the same as the number of b's in y.

In the second language, B, because there is a deterministic choice of what the string x contains and what the string y contains, actual counting is required to compare the number of a's in x with the number of b's in y, which for an arbitrarily large number of a's and b's, a finite automaton cannot be constructed. Pumping Lemma may be used to prove this language non-regular.

15 Sep 2016 - 11:07am

Oh. I see. Well in that case, it cannot be said. Halting of the Turing machine for finite length input is not assured. 

30 Aug 2016 - 6:30pm

Well, I think I may have misunderstood. 

I thought, you were asking: " If the TM always halts on inputs of length less than 100, then is the language of the TM decidable?" The answer to this is YES.
However, if the TM has inputs of length greater than 100, and we do not know what happens with those inputs, then nothing can be said about the decidability of the language of the TM.

30 Aug 2016 - 11:40am

If any TM is guaranteed to halt in a finite amount of  time, then the language it recognizes is also decidable.

30 Aug 2016 - 10:45am