File:An automat accepting the language a(bc)*d.svg
Original file (SVG file, nominally 170 × 100 pixels, file size: 8 KB)
Captions
DescriptionAn automat accepting the language a(bc)*d.svg |
The image shows a finite state automaton (FSA). The FSA accepts the string: abcd. Since this string has a length which is at least as large as the number of states, which is four, the pigeonhole principle indicates that there must be at least one repeated state among the start state and the next four visited states. In this example, only q1 is a repeated state. Since the substring bc takes the machine through transitions that start at state q1 and end at state q1, that portion could be repeated and the FSA would still accept, giving the string abcbcd. Alternatively, the bc portion could be removed and the FSA would still accept giving the string ad. In terms of the pumping lemma, the string abcd is broken into an x portion a, a y portion bc and a z portion d. |
Date | (UTC) |
Source | |
Author |
|
This is a retouched picture, which means that it has been digitally altered from its original version. Modifications: Vectorized. The original can be viewed here: An automat accepting the language a(bc)*d.png: . Modifications made by Jkwchui.
|
This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license. | ||
| ||
This licensing tag was added to this file as part of the GFDL licensing update.http://creativecommons.org/licenses/by-sa/3.0/CC BY-SA 3.0Creative Commons Attribution-Share Alike 3.0truetrue |
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled GNU Free Documentation License.http://www.gnu.org/copyleft/fdl.htmlGFDLGNU Free Documentation Licensetruetrue |
Original upload log[edit]
This image is a derivative work of the following images:
- File:An_automat_accepting_the_language_a(bc)*d.png licensed with Cc-by-sa-3.0-migrated, GFDL
- 2005-08-30T06:08:58Z Yuval Madar 314x165 (6770 Bytes) I created this image myself using [http://www.jflap.org/ JFLAP].
Uploaded with derivativeFX
File history
Click on a date/time to view the file as it appeared at that time.
Date/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 18:22, 30 January 2011 | 170 × 100 (8 KB) | Jkwchui (talk | contribs) | {{Information |Description=The image shows a finite state automaton (FSA). The FSA accepts the string: '''abcd'''. Since this string has a length which is at least as large as the number of states, which is four, the pigeonhole principle indicates |
You cannot overwrite this file.
File usage on Commons
The following 2 pages use this file:
File usage on other wikis
The following other wikis use this file:
- Usage on en.wikipedia.org
- Usage on fa.wikipedia.org
- Usage on pt.wikipedia.org
Metadata
This file contains additional information such as Exif metadata which may have been added by the digital camera, scanner, or software program used to create or digitize it. If the file has been modified from its original state, some details such as the timestamp may not fully reflect those of the original file. The timestamp is only as accurate as the clock in the camera, and it may be completely wrong.
Width | 170.481px |
---|---|
Height | 100.222px |