502 views
0 votes
0 votes
to check if a given language is regular or not, for this i have seen many solutions on the net and lectures but everyone has used a direct approach to determine that but in the standard textbooks the method for doing this is given as pumping lemma which i don't know how to apply in the questions but direct method i've understood. would this be enough for gate if they invent a new question and i don't know the concept to solve it. which one should i do, pumping lemma or the direct approach one?

1 Answer

Best answer
0 votes
0 votes
the pumping lemma is not hard to understand , its the extended version of pigeon hole priciple .  iam writing here the answer please look   and if you have any doubt ask me

1. since before this you have to understand the pigionhole priciple as this will come handy to understand the what actually happening in the pummping lemma.  say the given language is regular , since its regular , it could be finite or infinite depending upon the langugage . bear with me you will understand . if the langugae is finite you could easily tell that the languge i regular or not but problem arises when you  get an infinite language. now as said we assumed that the language is regular and if its infinite or finite in both cases we could contruct its dfa. Now dfa has finite states now take a string that belongs to the language but  have length greater than total states of dfa , to put this string in dfa we have to put more than one string in a single state that is a loop exists . since the loop can exist on any of the given alphabet we need to choose different possiblities , but  this can be done easily if you can look to the language given . now since we have loop it should accept more  string of the same alphabets when looped and  if not then the langugage is not regular  if it does then the language is regular but look to cover other alphabet if looped and rule all the possiblities . the above method is formally called as pummpimg lemma ,  and because of above language its easy to prove irregular languge irregular rather than regular as regular
selected by

Related questions

0 votes
0 votes
0 answers
1
jg662 asked Feb 22
87 views
Use the Pumping Lemma to show that the following languages over Σ={�,�}Σ={a,b} are not regular. In each case, carefully describe the string that will be pumped and ...
0 votes
0 votes
1 answer
4
shallowfalcon asked Oct 17, 2022
438 views
If L = { x == y | where x and y are equal binary numbers} and Σ = {0, 1, =}How can I prove that L is not a regular language using pumping lemma and contradiction?