About

Antonio is a Ph.D. student at the Indian Institute of Technology - Kharagpur. He scored 99.93 percentile in the GATE examination in 2012. He completed his Bachelor of Engineering in the Goa Engineering College (Gold medalist), and thereafter worked as a Web Developed in Persistent Systems for two years. In 2012 he chose to complete his M.Tech at IIT-Kharagpur in Computer Sci & Engg, which he completed with the top rank in the department (Institute Silver Medalist). Soon after his Masters, he joined the Ph.D. program at IIT-Kharagpur. His research interests lie in the area of Formal Methods and Automata Theory.

Role

Alma Mater:

Bachelors in Computer Engineering
Goa Engineering College, Farmagudi
2006 to 2010
M.Tech in Computer Science and Engineering
IIT Kharagpur
2012 to 2014

Experience:

software engineer
Persistent Systems
2010 to 2012
Research Intern
Texas Instruments
2014
Research Intern
VERIMAG Laboratory France
2014
Tud
Answer
8 months 2 weeks ago

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.

moreless
Tud
Video lecture
1 year 5 months ago

So let me clarify this. A language having the same start and end symbol can be of length one.  However,  under the assumption that the start and end symbols must be identical and must not be in the same position,  ie not the string is not of length one, then what you are saying is applicable. So I perhaps should have made the definition  of the language clearer. 

morelessWatch Now
Tud
Answer
1 year 5 months ago

@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.

moreless
Tud
Answer
1 year 5 months ago

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^+\)

moreless
Tud
Answer
1 year 5 months ago

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.

moreless
ranita's picture
Ranita Biswas
pritam's picture
Pritam Prasun
techtud's picture
Techtud Admin
1
pritam's picture
Pritam Prasun
905
manishsingh's picture
Manish Singh
1249
jaipoornasingh's picture
Jaipoorna Singh
1350
ramsharma's picture
Ram Sharma
1723
parthshah's picture
Parth Shah
2086
chitra ambu
2104
akshaybhudke's picture
Akshay bhudke
2382
parimal_andhalkar's picture
Parimal Andhalkar
2408
ish5634426's picture
ishwar chandra mahto
2630
Chinmay
3052
anshul's picture
Anshul Mittal
3500
vivek gupta
3911
syamap's picture
syama
4302
shreyasdawkhare's picture
Shreyas Dawkhare
5216

Pages

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.

more less
23 Jan 2017 - 11:44pm

@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.

more less
23 Jan 2017 - 8:35pm

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^+\)

more less
20 Jan 2017 - 12:42pm

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.

more less
18 Sep 2016 - 1:54am

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.

Therefore, 

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

more less
15 Sep 2016 - 11:07am

@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.

more less

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

more less

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.

more less

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

more less
18 Jan 2016 - 6:26pm

There can not be any 1's after the r 0's. Such strings having any ones after the r zeroes would need to be rejected by going to a dead state on reading a 1 after reading p zeroes, q>0 ones, and r zeroes.

more less

Pages