Pumping Lemma for Context Free Languages || Lesson 77 || Finite Automata || Learning Monkey ||
8.2 هزار بار بازدید -
3 سال پیش
-
Pumping Lemma for Context Free
Pumping Lemma for Context Free Languages
In this class, We discuss Pumping Lemma for Context-Free Languages.
The reader should have prior knowledge of pumping lemma for regular languages. Click Here.
First, refresh the concept of pumping lemma for regular languages.
Along with the concept, we come into pumping lemma for context-free languages.
The language aⁿbⁿ is a context-free language, and it is not a regular language.
Why is aⁿbⁿ not a regular language?
In the language L = aⁿbⁿ we count the equivalence of a and b.
Counting is not possible in finite automata because we do not have memory in finite automata.
But in context-free languages, we had a stack memory. So we can check the equivalence count.
To prove the given language is not regular. We followed as below.
Take input string aaabbb.
We divide the string into x(y)ⁱz. We have taken aa(a)ⁱbbb.
We keep on pumping y.
We need to generate the strings present in the language L.
In the above example, we keep on pumping a.
As i value increases, a’s are increasing.
Regular languages can not do equivalence count for two variables. So we have taken a single pumping variable.
For the same language, if we divide the string into five parts.
The below example shows two pumping variables.
Example: Take aaabbb.
Divide the string as u(v)ⁱw(x)ⁱy.
a(a)ⁱa(b)ⁱbb
For i = 1 we get aaabbb
For i = 2 we get aaaabbbb
If we take two pumping variables, we can not prove the given language does not belong to the regular language.
The context-free languages can do equivalence of two symbols.
The language L1 = aⁿbⁿcⁿ is not a context-free language.
The language L1 is doing an equivalence count of three symbols, and we can not do this using two pumping variables.
So to prove the language is not a context-free language, we choose two pumping variables.
Pumping Lemma: We use a pumping lemma to show the given language is not a Context-Free Language.
We divide the given input string into five parts. u(v)ⁱw(x)ⁱy.
We follow the conditions.
1) |vx| gt= 0
2) |vwx| lt=n
The first condition says you do not take epsilon for variables v and x.
No use if we take epsilon for both pumping variables.
The middle string vwx should be less than or equal to n.
We can take any n value.
To make the middle part as short as possible, we chose the n value.
Take n = 3.
The input string is aaabbbccc.
With n=3, The middle part vwx can take different possibilities.
The middle part vwx can take only a’s or only b’s or c’s, a combination of a and b, or a combination of b and c.
The above possibilities are enough to show that the given language is not context-free.
Possibility 1: a(a)ⁱa(b)ⁱbb
For i = 1 we get aaabbbccc
For i = 2 we get aaaabbbbccc
For i =2, we did not get the string present in our language
Possibility 2: aaab(b)ⁱb(c)ⁱcc
For i = 1 we get aaabbbccc
For i = 2 we get aaabbbbcccc
For i =2, we did not get the string present in our language.
Link for playlists:
@learningmonkey
Link for our website: https://learningmonkey.in
Follow us on Facebook @ Facebook: learningmonkey
Follow us on Instagram @ Instagram: learningmonkey1
Follow us on Twitter @ Twitter: _learningmonkey
Mail us @ [email protected]
In this class, We discuss Pumping Lemma for Context-Free Languages.
The reader should have prior knowledge of pumping lemma for regular languages. Click Here.
First, refresh the concept of pumping lemma for regular languages.
Along with the concept, we come into pumping lemma for context-free languages.
The language aⁿbⁿ is a context-free language, and it is not a regular language.
Why is aⁿbⁿ not a regular language?
In the language L = aⁿbⁿ we count the equivalence of a and b.
Counting is not possible in finite automata because we do not have memory in finite automata.
But in context-free languages, we had a stack memory. So we can check the equivalence count.
To prove the given language is not regular. We followed as below.
Take input string aaabbb.
We divide the string into x(y)ⁱz. We have taken aa(a)ⁱbbb.
We keep on pumping y.
We need to generate the strings present in the language L.
In the above example, we keep on pumping a.
As i value increases, a’s are increasing.
Regular languages can not do equivalence count for two variables. So we have taken a single pumping variable.
For the same language, if we divide the string into five parts.
The below example shows two pumping variables.
Example: Take aaabbb.
Divide the string as u(v)ⁱw(x)ⁱy.
a(a)ⁱa(b)ⁱbb
For i = 1 we get aaabbb
For i = 2 we get aaaabbbb
If we take two pumping variables, we can not prove the given language does not belong to the regular language.
The context-free languages can do equivalence of two symbols.
The language L1 = aⁿbⁿcⁿ is not a context-free language.
The language L1 is doing an equivalence count of three symbols, and we can not do this using two pumping variables.
So to prove the language is not a context-free language, we choose two pumping variables.
Pumping Lemma: We use a pumping lemma to show the given language is not a Context-Free Language.
We divide the given input string into five parts. u(v)ⁱw(x)ⁱy.
We follow the conditions.
1) |vx| gt= 0
2) |vwx| lt=n
The first condition says you do not take epsilon for variables v and x.
No use if we take epsilon for both pumping variables.
The middle string vwx should be less than or equal to n.
We can take any n value.
To make the middle part as short as possible, we chose the n value.
Take n = 3.
The input string is aaabbbccc.
With n=3, The middle part vwx can take different possibilities.
The middle part vwx can take only a’s or only b’s or c’s, a combination of a and b, or a combination of b and c.
The above possibilities are enough to show that the given language is not context-free.
Possibility 1: a(a)ⁱa(b)ⁱbb
For i = 1 we get aaabbbccc
For i = 2 we get aaaabbbbccc
For i =2, we did not get the string present in our language
Possibility 2: aaab(b)ⁱb(c)ⁱcc
For i = 1 we get aaabbbccc
For i = 2 we get aaabbbbcccc
For i =2, we did not get the string present in our language.
Link for playlists:
@learningmonkey
Link for our website: https://learningmonkey.in
Follow us on Facebook @ Facebook: learningmonkey
Follow us on Instagram @ Instagram: learningmonkey1
Follow us on Twitter @ Twitter: _learningmonkey
Mail us @ [email protected]
3 سال پیش
در تاریخ 1400/11/06 منتشر شده
است.
8,264
بـار بازدید شده