In a CS course I"m taking there is an example of a language that is not regular:

a^nb^n I can understand that it is not regular since no Finite State Automaton/Machine can be written that validates and accepts this input đầu vào since it lacks a memory component. (Please correct me if I"m wrong)

The wikipedia entry on Regular Language also lists this example, but does not provide a (mathematical) proof why it is not regular.

Can anyone enlighten me on this và provide proof for this, or point me too a good resource?




Bạn đang xem:

computer-science fsm regular-language
cốt truyện
Follow
edited May 18, 2010 at 13:39
*

Grace Note♦
3,16544 gold badges3434 silver badges5454 bronze badges
asked Feb 22, 2010 at 8:52
*

Christophe HerremanChristophe Herreman
15.6k77 gold badges5757 silver badges8686 bronze badges
showroom a bình luận |

7 Answers 7


Sorted by: Reset to default
Highest score (default) Date modified (newest first) Date created (oldest first)
18
What you"re looking for is Pumping lemma for regular languages.

Here is an example with your exact problem:

Examples: Let L = m ≥ 1. Then L is not regular. Proof: Let n be as in Pumping Lemma. Let w = anbn. Let w = xyz be as in Pumping Lemma. Thus, xy2z ∈ L, however, xy2z contains more a’s than b’s.


giới thiệu
Follow
edited Mar 26, 2019 at 18:17
*

Lucas
45622 gold badges1111 silver badges1515 bronze badges
answered Feb 22, 2010 at 8:53
*

cletuscletus
599k161161 gold badges897897 silver badges938938 bronze badges
4
showroom a phản hồi |
8
Because you can"t write a finite state machine that will "count" identical sequences of "a" & "b" symbols. In a nutshell, FSMs cannot "count". Try imagining such a FSM: how many states would you give lớn symbol "a"? How many khổng lồ "b"? What if your input đầu vào sequence has more?

Note that if you had n


*








*








*



*









*









Xem thêm: I'M Falling In Love Là Gì Và Cấu Trúc Fall In Love Trong Tiếng Anh


*








*

Sujai DevSujai Dev








Submit








































Question feed
Question feed to subscribe to this RSS feed, copy and paste this URL into your RSS reader.









Xem thêm: Tìm Hệ Số Của X8 Trong Khai Triển Đa Thức F(X), Tìm Hệ Số Cuả X ^ 8 Trong Khai Triển Đa Thức F(X)

Site thiết kế / logo sản phẩm © 2022 Stack Exchange Inc; user contributions licensed under cc by-sa. Rev2022.6.10.42345


Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.