为什么 a^mb^n 其中 m,n > 0 是常规语言，但 a^nb^n 其中 n > 0 是非常规语言

发布于 2025-01-19 12:44:46 字数 137 浏览 4 评论 0 原文

a^mb^n (其中 m,n >= 0) 是常规语言，但为什么 a^nb^n (其中 n >= 0) 是非常规语言？在这两种语言中，我们都采用无限数量的 a 和 b，但是为什么我们可以为第一种情况构建有限自动机，而不能为第二种情况构建有限自动机？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

雪化雨蝶 2025-01-26 12:44:47

让我们将上述语言视为A，B：

X = a^m b^n where m,n>0 
Y = a^n b^n where n>0

语言 X 是一种常规语言，但是语言 y 不是一种常规语言，因为我们无法为语言构建有限的自动机 y 。

如果语言不满足泵送引理，则语言不是常规语言，但是如果该语言满足泵送引理，则该语言不必是规律的。

如果语言 x A和B的数量不同，因此我们不必记住“ A”的发生数量，在接受所有A之后，我们可以接受B并转移到最终状态，而是语言 y A和B的数量相同。因此，语言中的所有字符串都应包含相等数量的A和相等数量的B。因此，我们需要记住A的数量，以便可以评估B的数量，这是使用有限自动机无法进行的。
因此，为了评估TESE的语言，需要按下自动机。

PushDown automata = Finite automata + some amount of memory(stack).

类型的语言 y 称为上下文免费语言，可以使用俯卧撑自动机（PDA）对其进行评估。FiniteAutomata没有任何存储器来存储A和B的计数。作为下降自动机具有一定数量的内存，因此我们可以评估 y 类型的语言。

对于这种语言 y ，我们需要将所有A启动到堆栈中，每当我们遇到B时，我们都需要弹出A（请记住所有A必须在B的情况下）。 A不是在B之前，我们需要将系统移至死状态。

Let us consider the above languages as A,B:

X = a^m b^n where m,n>0 
Y = a^n b^n where n>0

Language X is a regular language but Language Y is not a regular language because we cannot construct a Finite automata for language Y.

A language is not a regular language if the language does not satisfy the pumping lemma , but if the language satisfies the pumping lemma then the language need not be regular.

In case of language X the number of a's and b's are different so we need not remember number of occurrences of 'a' after accepting all a's we can accept b's and move to final state ,but in case of language Y the number of a's and b's are same. So all the strings in the language Y should contain equal number of a's and equal number of b's. So we need to remember the number of a's so that b's can be evaluated, which is not possible using finite automata.
So to evaluate tese kind of languages push down automata is required.

PushDown automata = Finite automata + some amount of memory(stack).

The languages of the kind Y are called context free language and they can be evaluated using Pushdown Automata(PDA).Finite automata do not have any memory to store the count of a's and b's. where as pushdown automata has some amount of memory so we can evaluate languages of type Y.

For this language Y we need to push all the a's on to the stack and whenever we encounter b's then we need to pop a's(remembering the condition that all the a's must be before b's).If all the a's are not before b's then we need to move the system to dead state.

回复收藏 0 原文

烙印 2025-01-26 12:44:47

在第二语言中，A和B的数量必须相同。
有限的自动机需要计算A的数量来检查B的数量是否相同。这将需要无限的状态。

也许可以在Wikipedia上查看泵送引理： nofollow noreferrer“> a>

回复收藏 0 原文

乜一 2025-01-26 12:44:47

By using pumping lemma we have to proove the above language is not a regular language
L=a^nb^n
n->is the no.of states
We have to solve this problem by using two methods
1.one way is to simply considering an example
2.another way is to by simply substituting the i values in uv^iw
First we have to take Z=a^nb^n
And then Z=uv^iw
v is a substring
For example n=1
•Z=ab
n=2
•Z=aabb
n=3
•Z=aaabbb
The selection of v comes under 3 cases
For example
Case1:
v is a substring only a`s
 For example assume v=a^x
x is the no.of repetitions
•Z is written in uv^iw
If i=0
Z=a^n-x.1.b^n does not belongs to L
Case2:
Consider only b`s
Assume v=b^x
For i=0
Z=a^nb^n-x does not belongs to L
Case3:
Consider only a`sb`s
Assume v=a^xb^x
For i=0
Z=a^n-xb^n-x€L
For i=1
Z=a^n-xa^xb^xb^n-x
 =a^nb^n€L
For i=2
Z=a^n-x(a^xb^x)^2b^n-x
 =a^n-xa^xb^xa^xb^xb^n-x doesn't belongs to L
 The string start with always a`s followed by b`s
We are getting one more additional ab (or) ba but our string of Length n.
So above the three conditions are not satisfiying so...The given Language is not a regular language



In the first case..a^mb^n m and n are not equal m may be Greater than n or less than n or may be equal to n ...so..it is a regular language...

By using pumping lemma we have to proove the above language is not a regular language
L=a^nb^n
n->is the no.of states
We have to solve this problem by using two methods
1.one way is to simply considering an example
2.another way is to by simply substituting the i values in uv^iw
First we have to take Z=a^nb^n
And then Z=uv^iw
v is a substring
For example n=1
•Z=ab
n=2
•Z=aabb
n=3
•Z=aaabbb
The selection of v comes under 3 cases
For example
Case1:
v is a substring only a`s
 For example assume v=a^x
x is the no.of repetitions
•Z is written in uv^iw
If i=0
Z=a^n-x.1.b^n does not belongs to L
Case2:
Consider only b`s
Assume v=b^x
For i=0
Z=a^nb^n-x does not belongs to L
Case3:
Consider only a`sb`s
Assume v=a^xb^x
For i=0
Z=a^n-xb^n-x€L
For i=1
Z=a^n-xa^xb^xb^n-x
 =a^nb^n€L
For i=2
Z=a^n-x(a^xb^x)^2b^n-x
 =a^n-xa^xb^xa^xb^xb^n-x doesn't belongs to L
 The string start with always a`s followed by b`s
We are getting one more additional ab (or) ba but our string of Length n.
So above the three conditions are not satisfiying so...The given Language is not a regular language



In the first case..a^mb^n m and n are not equal m may be Greater than n or less than n or may be equal to n ...so..it is a regular language...

回复收藏 0 原文

~没有更多了~