Register

gate-2015 Arden's theorem Doubt

• reshown by
1,714 views
0 0 votes

https://gateoverflow.in/8159/gate2015-2-35

What are these equations?

$X_0 = 1 X_1$

$X_1 = 0 X_1 + 1 X_2$

$X_2 = 0 X_1 + \{ \lambda \}$

Can we treat them as RIGHT LINEAR GRAMMAR? If yes, then this is the FA for it.Now the question asks for the language of $X_0$ which will be NULL.

.

The correct language of $X_0$ can be obtained by REVERSAL of this FA. i.e. by reversing arrows and swapping initial and final states.

I know that when a LEFT LINEAR GRAMMAR is changed to RIGHT LINEAR then language is reversed. But why here?

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · Gateforum Test Serie...Next → · ME TEST SERIES
← Previous in category · Test seriesNext in category → · toc(undecidability)
Position:
Show:

Related questions

0 0 votes
0 0 answers
837
837 views
Deepanshu asked Nov 14, 2018
837 views
SELF DOUBT _ RICE THEOREM
L1 = { <M | M is a TM and | L (M) <=1 }L2= { <M | M is a TM and | L (M) >=1 }NOW QUESTION IS WHICH ARE RECURSIVE ENUMERABLE AND WHICH ARE NOT ????I JUST READ BASICS OF ...
0 0 votes
0 0 answers
833
833 views
Durgesh Singh asked Dec 14, 2017
833 views
Doubt in Rice's Theorem
I have a doubt while understanding step 2 in proof of Rice's Theorem-According to my understanding,proof of Rice's theorem as follows ( Please suggest If something is wro...
2 2 votes
1 1 answer
1.2k
1.2k views
rahul sharma 5 asked Jan 22, 2017
1,235 views
General Doubt In rice theorem
If we are not able to apply non-monote property ,then is it always true that it is RE but not REC,are there any scenarios where we can't apply non-monotone property but s...
2 2 votes
0 0 answers
1.2k
1.2k views
Xylene asked Nov 25, 2016
1,208 views
Basic Doubt in Rice Theorem
I read this blog http://gatecse.in/rices-theorem/ and I have a doubt in the first property.An example in this blog is L(M) = {0} and it's written that TMno =sigma* . My d...