1,071 views
3 votes
3 votes
how to find an infinite language is regular or not is there any other method than drawing DFA as DFA made by us may or may not be correct how to ensure DFA is  correct and language is regular

1 Answer

Best answer
3 votes
3 votes
It is rather easy to check whether an infinite language is non-regular or not. Here are a few tips:

Check whether any alphabet /string comparisons are being done. If yes, then non-regular.

Check whether any counting process is involved that requires a stack to remember alphabets. If yes, then non-regular.

Check whether any non-linear powers are involved in any alphabet. If yes, then non-regular

A sure method is to draw the DFA/NFA and write the correct regular expression. If this is possible, then regular.

To check whether a DFA is correct or not is to ensure that it accepts strings $a\in L$ and rejects strings $a\notin L$.
selected by

Related questions

0 votes
0 votes
1 answer
1
sumit kumar asked Jun 22, 2015
7,995 views
my question is whether we have a shortcut an idea which can help us in recognizing any language to be regular or not,in GATE .and also what is the best way to get it prop...
2 votes
2 votes
1 answer
2
Riya Roy(Arayana) asked Oct 18, 2015
5,683 views
Can someone give the intuition behind this ? Moreover an example will also be helpful ..
1 votes
1 votes
1 answer
3
2 votes
2 votes
2 answers
4
Kaushal28 asked Sep 21, 2016
2,303 views
If any grammer is given, how can we tell that the grammar is regular or not? Is that any perticular method?