CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-disabled skin-theme-clientpref-day vector-toc-available" lang="it" dir="ltr"> <head> <meta charset="UTF-8"> <title>Grammatica regolare - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-disabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )itwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":[",\t."," \t,"],"wgDigitTransformTable":["",""], "wgDefaultDateFormat":"dmy","wgMonthNames":["","gennaio","febbraio","marzo","aprile","maggio","giugno","luglio","agosto","settembre","ottobre","novembre","dicembre"],"wgRequestId":"b80c8b62-283d-4670-9197-127010c12c14","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Grammatica_regolare","wgTitle":"Grammatica regolare","wgCurRevisionId":139475211,"wgRevisionId":139475211,"wgArticleId":2212,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Pagine che utilizzano collegamenti magici ISBN","Teoria dei linguaggi formali"],"wgPageViewLanguage":"it","wgPageContentLanguage":"it","wgPageContentModel":"wikitext","wgRelevantPageName":"Grammatica_regolare","wgRelevantArticleId":2212,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgMediaViewerOnClick": true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"it","pageLanguageDir":"ltr","pageVariantFallbacks":"it"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":5000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q645527","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.gadget.coloriDarkMode-default":"ready","ext.globalCssJs.user.styles":"ready", "site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.MainPageWikiList","ext.gadget.stru-commonsupload","ext.gadget.HiddenCat","ext.gadget.ReferenceTooltips","ext.gadget.TitoloErrato","ext.gadget.NewSection","ext.gadget.RichiediRevisioneBozza","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents", "ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=it&modules=ext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=it&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=it&modules=ext.gadget.coloriDarkMode-default&only=styles&skin=vector-2022"> <link rel="stylesheet" href="/w/load.php?lang=it&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.5"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/2/26/Gerarchia-di-Chomsky.jpg"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1203"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/2/26/Gerarchia-di-Chomsky.jpg"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="802"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="642"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Grammatica regolare - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//it.m.wikipedia.org/wiki/Grammatica_regolare"> <link rel="alternate" type="application/x-wiki" title="Modifica" href="/w/index.php?title=Grammatica_regolare&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (it)"> <link rel="EditURI" type="application/rsd+xml" href="//it.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://it.wikipedia.org/wiki/Grammatica_regolare"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.it"> <link rel="alternate" type="application/atom+xml" title="Feed Atom di Wikipedia" href="/w/index.php?title=Speciale:UltimeModifiche&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Grammatica_regolare rootpage-Grammatica_regolare skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Vai al contenuto</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Sito"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Menu principale" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Menu principale</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Menu principale</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">sposta nella barra laterale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">nascondi</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigazione </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Pagina_principale" title="Visita la pagina principale [z]" accesskey="z"><span>Pagina principale</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Speciale:UltimeModifiche" title="Elenco delle ultime modifiche del sito [r]" accesskey="r"><span>Ultime modifiche</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Speciale:PaginaCasuale" title="Mostra una pagina a caso [x]" accesskey="x"><span>Una voce a caso</span></a></li><li id="n-nearby-pages-title" class="mw-list-item"><a href="/wiki/Speciale:NelleVicinanze"><span>Nelle vicinanze</span></a></li><li id="n-vetrina" class="mw-list-item"><a href="/wiki/Wikipedia:Vetrina"><span>Vetrina</span></a></li><li id="n-help" class="mw-list-item"><a href="/wiki/Aiuto:Aiuto" title="Pagine di aiuto"><span>Aiuto</span></a></li><li id="n-Sportello-informazioni" class="mw-list-item"><a href="/wiki/Aiuto:Sportello_informazioni"><span>Sportello informazioni</span></a></li> </ul> </div> </div> <div id="p-Comunità" class="vector-menu mw-portlet mw-portlet-Comunità" > <div class="vector-menu-heading"> Comunità </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-portal" class="mw-list-item"><a href="/wiki/Portale:Comunit%C3%A0" title="Descrizione del progetto, cosa puoi fare, dove trovare le cose"><span>Portale Comunità</span></a></li><li id="n-villagepump" class="mw-list-item"><a href="/wiki/Wikipedia:Bar"><span>Bar</span></a></li><li id="n-wikipediano" class="mw-list-item"><a href="/wiki/Wikipedia:Wikipediano"><span>Il Wikipediano</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="/wiki/Wikipedia:Contatti"><span>Contatti</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Pagina_principale" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="L'enciclopedia libera" src="/static/images/mobile/copyright/wikipedia-tagline-it.svg" width="120" height="13" style="width: 7.5em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Speciale:Ricerca" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Cerca in Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Ricerca</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Cerca in Wikipedia" aria-label="Cerca in Wikipedia" autocapitalize="sentences" title="Cerca in Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Speciale:Ricerca"> </div> <button class="cdx-button cdx-search-input__end-button">Ricerca</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Strumenti personali"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Aspetto"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Modifica la dimensione, la larghezza e il colore del testo" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Aspetto" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Aspetto</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_it.wikipedia.org&uselang=it" class=""><span>Fai una donazione</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Speciale:CreaUtenza&returnto=Grammatica+regolare" title="Si consiglia di registrarsi e di effettuare l'accesso, anche se non è obbligatorio" class=""><span>registrati</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Speciale:Entra&returnto=Grammatica+regolare" title="Si consiglia di effettuare l'accesso, anche se non è obbligatorio [o]" accesskey="o" class=""><span>entra</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Altre opzioni" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Strumenti personali" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Strumenti personali</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="Menu utente" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_it.wikipedia.org&uselang=it"><span>Fai una donazione</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Speciale:CreaUtenza&returnto=Grammatica+regolare" title="Si consiglia di registrarsi e di effettuare l'accesso, anche se non è obbligatorio"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>registrati</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Speciale:Entra&returnto=Grammatica+regolare" title="Si consiglia di effettuare l'accesso, anche se non è obbligatorio [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>entra</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pagine per utenti anonimi <a href="/wiki/Aiuto:Benvenuto" aria-label="Ulteriori informazioni sulla contribuzione"><span>ulteriori informazioni</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Speciale:MieiContributi" title="Un elenco delle modifiche fatte da questo indirizzo IP [y]" accesskey="y"><span>contributi</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Speciale:MieDiscussioni" title="Discussioni sulle modifiche fatte da questo indirizzo IP [n]" accesskey="n"><span>discussioni</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Sito"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Indice" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Indice</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">sposta nella barra laterale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">nascondi</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">Inizio</div> </a> </li> <li id="toc-Richiami" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Richiami"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Richiami</span> </div> </a> <ul id="toc-Richiami-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Definizione" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definizione"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Definizione</span> </div> </a> <ul id="toc-Definizione-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Esempi" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Esempi"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Esempi</span> </div> </a> <button aria-controls="toc-Esempi-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Attiva/disattiva la sottosezione Esempi</span> </button> <ul id="toc-Esempi-sublist" class="vector-toc-list"> <li id="toc-Esempio_di_grammatica_non_regolare" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Esempio_di_grammatica_non_regolare"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Esempio di grammatica non regolare</span> </div> </a> <ul id="toc-Esempio_di_grammatica_non_regolare-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Bibliografia" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Bibliografia"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Bibliografia</span> </div> </a> <ul id="toc-Bibliografia-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Voci_correlate" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Voci_correlate"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Voci correlate</span> </div> </a> <ul id="toc-Voci_correlate-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Indice" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Mostra/Nascondi l'indice" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Mostra/Nascondi l'indice</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Grammatica regolare</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Vai a una voce in un'altra lingua. Disponibile in 20 lingue" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-20" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">20 lingue</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Gram%C3%A0tica_regular" title="Gramàtica regular - catalano" lang="ca" hreflang="ca" data-title="Gramàtica regular" data-language-autonym="Català" data-language-local-name="catalano" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Regul%C3%A1rn%C3%AD_gramatika" title="Regulární gramatika - ceco" lang="cs" hreflang="cs" data-title="Regulární gramatika" data-language-autonym="Čeština" data-language-local-name="ceco" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Regul%C3%A4re_Grammatik" title="Reguläre Grammatik - tedesco" lang="de" hreflang="de" data-title="Reguläre Grammatik" data-language-autonym="Deutsch" data-language-local-name="tedesco" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikipedia.org/wiki/Regular_grammar" title="Regular grammar - inglese" lang="en" hreflang="en" data-title="Regular grammar" data-language-autonym="English" data-language-local-name="inglese" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Gram%C3%A1tica_regular" title="Gramática regular - spagnolo" lang="es" hreflang="es" data-title="Gramática regular" data-language-autonym="Español" data-language-local-name="spagnolo" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AF%D8%B3%D8%AA%D9%88%D8%B1_%D8%B2%D8%A8%D8%A7%D9%86_%D9%85%D9%86%D8%B8%D9%85" title="دستور زبان منظم - persiano" lang="fa" hreflang="fa" data-title="دستور زبان منظم" data-language-autonym="فارسی" data-language-local-name="persiano" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Grammaire_r%C3%A9guli%C3%A8re" title="Grammaire régulière - francese" lang="fr" hreflang="fr" data-title="Grammaire régulière" data-language-autonym="Français" data-language-local-name="francese" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%93%D7%A7%D7%93%D7%95%D7%A7_%D7%A8%D7%92%D7%95%D7%9C%D7%A8%D7%99" title="דקדוק רגולרי - ebraico" lang="he" hreflang="he" data-title="דקדוק רגולרי" data-language-autonym="עברית" data-language-local-name="ebraico" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/Regularna_gramatika" title="Regularna gramatika - croato" lang="hr" hreflang="hr" data-title="Regularna gramatika" data-language-autonym="Hrvatski" data-language-local-name="croato" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E6%AD%A3%E8%A6%8F%E6%96%87%E6%B3%95" title="正規文法 - giapponese" lang="ja" hreflang="ja" data-title="正規文法" data-language-autonym="日本語" data-language-local-name="giapponese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%A0%95%EA%B7%9C_%EB%AC%B8%EB%B2%95" title="정규 문법 - coreano" lang="ko" hreflang="ko" data-title="정규 문법" data-language-autonym="한국어" data-language-local-name="coreano" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-mwl mw-list-item"><a href="https://mwl.wikipedia.org/wiki/Gram%C3%A1tica_regular" title="Gramática regular - mirandese" lang="mwl" hreflang="mwl" data-title="Gramática regular" data-language-autonym="Mirandés" data-language-local-name="mirandese" class="interlanguage-link-target"><span>Mirandés</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Reguliere_grammatica" title="Reguliere grammatica - olandese" lang="nl" hreflang="nl" data-title="Reguliere grammatica" data-language-autonym="Nederlands" data-language-local-name="olandese" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Gramatyka_regularna" title="Gramatyka regularna - polacco" lang="pl" hreflang="pl" data-title="Gramatyka regularna" data-language-autonym="Polski" data-language-local-name="polacco" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Gram%C3%A1tica_regular" title="Gramática regular - portoghese" lang="pt" hreflang="pt" data-title="Gramática regular" data-language-autonym="Português" data-language-local-name="portoghese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0" title="Регулярная грамматика - russo" lang="ru" hreflang="ru" data-title="Регулярная грамматика" data-language-autonym="Русский" data-language-local-name="russo" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Regul%C3%A1rna_gramatika" title="Regulárna gramatika - slovacco" lang="sk" hreflang="sk" data-title="Regulárna gramatika" data-language-autonym="Slovenčina" data-language-local-name="slovacco" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/Regularna_gramatika" title="Regularna gramatika - serbo" lang="sr" hreflang="sr" data-title="Regularna gramatika" data-language-autonym="Српски / srpski" data-language-local-name="serbo" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%B0_%D0%B3%D1%80%D0%B0%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0" title="Регулярна граматика - ucraino" lang="uk" hreflang="uk" data-title="Регулярна граматика" data-language-autonym="Українська" data-language-local-name="ucraino" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E6%AD%A3%E5%88%99%E6%96%87%E6%B3%95" title="正则文法 - cinese" lang="zh" hreflang="zh" data-title="正则文法" data-language-autonym="中文" data-language-local-name="cinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q645527#sitelinks-wikipedia" title="Modifica collegamenti interlinguistici" class="wbc-editpage">Modifica collegamenti</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespace"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Grammatica_regolare" title="Vedi la voce [c]" accesskey="c"><span>Voce</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Discussione:Grammatica_regolare" rel="discussion" title="Vedi le discussioni relative a questa pagina [t]" accesskey="t"><span>Discussione</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Cambia versione linguistica" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">italiano</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Visite"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Grammatica_regolare"><span>Leggi</span></a></li><li id="ca-ve-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Grammatica_regolare&veaction=edit" title="Modifica questa pagina [v]" accesskey="v"><span>Modifica</span></a></li><li id="ca-edit" class="collapsible vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Grammatica_regolare&action=edit" title="Modifica il wikitesto di questa pagina [e]" accesskey="e"><span>Modifica wikitesto</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Grammatica_regolare&action=history" title="Versioni precedenti di questa pagina [h]" accesskey="h"><span>Cronologia</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Strumenti pagine"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Strumenti" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Strumenti</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Strumenti</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">sposta nella barra laterale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">nascondi</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="Altre opzioni" > <div class="vector-menu-heading"> Azioni </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Grammatica_regolare"><span>Leggi</span></a></li><li id="ca-more-ve-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Grammatica_regolare&veaction=edit" title="Modifica questa pagina [v]" accesskey="v"><span>Modifica</span></a></li><li id="ca-more-edit" class="collapsible vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Grammatica_regolare&action=edit" title="Modifica il wikitesto di questa pagina [e]" accesskey="e"><span>Modifica wikitesto</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Grammatica_regolare&action=history"><span>Cronologia</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> Generale </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Speciale:PuntanoQui/Grammatica_regolare" title="Elenco di tutte le pagine che sono collegate a questa [j]" accesskey="j"><span>Puntano qui</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Speciale:ModificheCorrelate/Grammatica_regolare" rel="nofollow" title="Elenco delle ultime modifiche alle pagine collegate a questa [k]" accesskey="k"><span>Modifiche correlate</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Speciale:PagineSpeciali" title="Elenco di tutte le pagine speciali [q]" accesskey="q"><span>Pagine speciali</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Grammatica_regolare&oldid=139475211" title="Collegamento permanente a questa versione di questa pagina"><span>Link permanente</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Grammatica_regolare&action=info" title="Ulteriori informazioni su questa pagina"><span>Informazioni pagina</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Speciale:Cita&page=Grammatica_regolare&id=139475211&wpFormIdentifier=titleform" title="Informazioni su come citare questa pagina"><span>Cita questa voce</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Speciale:UrlShortener&url=https%3A%2F%2Fit.wikipedia.org%2Fwiki%2FGrammatica_regolare"><span>Ottieni URL breve</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Speciale:QrCode&url=https%3A%2F%2Fit.wikipedia.org%2Fwiki%2FGrammatica_regolare"><span>Scarica codice QR</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Stampa/esporta </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-create_a_book" class="mw-list-item"><a href="/w/index.php?title=Speciale:Libro&bookcmd=book_creator&referer=Grammatica+regolare"><span>Crea un libro</span></a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Speciale:DownloadAsPdf&page=Grammatica_regolare&action=show-download-screen"><span>Scarica come PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Grammatica_regolare&printable=yes" title="Versione stampabile di questa pagina [p]" accesskey="p"><span>Versione stampabile</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In altri progetti </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q645527" title="Collegamento all'elemento connesso dell'archivio dati [g]" accesskey="g"><span>Elemento Wikidata</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Strumenti pagine"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Aspetto"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Aspetto</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">sposta nella barra laterale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">nascondi</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">Da Wikipedia, l'enciclopedia libera.</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="it" dir="ltr"><figure class="mw-default-size mw-halign-right" typeof="mw:File"><a href="/wiki/File:Gerarchia-di-Chomsky.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/2/26/Gerarchia-di-Chomsky.jpg" decoding="async" width="364" height="365" class="mw-file-element" data-file-width="364" data-file-height="365" /></a><figcaption></figcaption></figure> <p>Una <b>grammatica regolare</b>, in informatica, è una <a href="/wiki/Grammatica_formale" title="Grammatica formale">grammatica formale</a> <a href="/wiki/Grammatica_generativa" title="Grammatica generativa">generativa</a>. Detta anche <b>lineare destra</b> o <b>lineare sinistra</b>, secondo la <a href="/wiki/Gerarchia_di_Chomsky" title="Gerarchia di Chomsky">gerarchia di Chomsky</a> è una grammatica di tipo-3. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Richiami">Richiami</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Grammatica_regolare&veaction=edit&section=1" title="Modifica la sezione Richiami" class="mw-editsection-visualeditor"><span>modifica</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Grammatica_regolare&action=edit&section=1" title="Edit section's source code: Richiami"><span>modifica wikitesto</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r130657691">body:not(.skin-minerva) .mw-parser-output .vedi-anche{font-size:95%}</style><style data-mw-deduplicate="TemplateStyles:r139142988">.mw-parser-output .hatnote-content{align-items:center;display:flex}.mw-parser-output .hatnote-icon{flex-shrink:0}.mw-parser-output .hatnote-icon img{display:flex}.mw-parser-output .hatnote-text{font-style:italic}body:not(.skin-minerva) .mw-parser-output .hatnote{border:1px solid #CCC;display:flex;margin:.5em 0;padding:.2em .5em}body:not(.skin-minerva) .mw-parser-output .hatnote-text{padding-left:.5em}body.skin-minerva .mw-parser-output .hatnote-icon{padding-right:8px}body.skin-minerva .mw-parser-output .hatnote-icon img{height:auto;width:16px}body.skin--responsive .mw-parser-output .hatnote a.new{color:#d73333}body.skin--responsive .mw-parser-output .hatnote a.new:visited{color:#a55858}</style> <div class="hatnote noprint vedi-anche"> <div class="hatnote-content"><span class="noviewer hatnote-icon" typeof="mw:File"><span><img src="//upload.wikimedia.org/wikipedia/commons/thumb/8/87/Magnifying_glass_icon_mgx2.svg/18px-Magnifying_glass_icon_mgx2.svg.png" decoding="async" width="18" height="18" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/8/87/Magnifying_glass_icon_mgx2.svg/27px-Magnifying_glass_icon_mgx2.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/8/87/Magnifying_glass_icon_mgx2.svg/36px-Magnifying_glass_icon_mgx2.svg.png 2x" data-file-width="286" data-file-height="280" /></span></span> <span class="hatnote-text">Lo stesso argomento in dettaglio: <b><a href="/wiki/Grammatica_formale" title="Grammatica formale">Grammatica formale</a></b>.</span></div> </div> <p>Come le altre grammatiche formali, è una <a href="/wiki/N-pla" class="mw-redirect" title="N-pla">quadrupla</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {G}}=\left\langle N,\Sigma ,P,S\right\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">G</mi> </mrow> </mrow> <mo>=</mo> <mrow> <mo>⟨</mo> <mrow> <mi>N</mi> <mo>,</mo> <mi mathvariant="normal">Σ</mi> <mo>,</mo> <mi>P</mi> <mo>,</mo> <mi>S</mi> </mrow> <mo>⟩</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {G}}=\left\langle N,\Sigma ,P,S\right\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7bb10550ee1683291b17c787c075fbf4ba146f41" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.388ex; height:2.843ex;" alt="{\displaystyle {\mathcal {G}}=\left\langle N,\Sigma ,P,S\right\rangle }"></span>, in cui </p> <ol><li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> sono i simboli non terminali</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Σ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e1f558f53cda207614abdf90162266c70bc5c1e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }"></span> sono i simboli terminali</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\in N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo>∈</mo> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S\in N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2825a0c08fd40c09a8c56df85454e574e1d4453f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.404ex; height:2.176ex;" alt="{\displaystyle S\in N}"></span> detto <i>assioma</i> è il simbolo non terminale di inizio.</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}"></span> sono le regole di produzione, una relazione binaria di cardinalità finita su <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N\cup \Sigma )^{*}\circ N\circ (N\cup \Sigma )^{*}\times (N\cup \Sigma )^{*}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>N</mi> <mo>∪</mo> <mi mathvariant="normal">Σ</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> <mo>∘</mo> <mi>N</mi> <mo>∘</mo> <mo stretchy="false">(</mo> <mi>N</mi> <mo>∪</mo> <mi mathvariant="normal">Σ</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> <mo>×</mo> <mo stretchy="false">(</mo> <mi>N</mi> <mo>∪</mo> <mi mathvariant="normal">Σ</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (N\cup \Sigma )^{*}\circ N\circ (N\cup \Sigma )^{*}\times (N\cup \Sigma )^{*}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f855ab15b0a09052e4f36f60fdcba60f6d2fd79e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.857ex; height:2.843ex;" alt="{\displaystyle (N\cup \Sigma )^{*}\circ N\circ (N\cup \Sigma )^{*}\times (N\cup \Sigma )^{*}}"></span>, che normalmente scriviamo come <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha \to \beta }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>α</mi> <mo stretchy="false">→</mo> <mi>β</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha \to \beta }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0cea747f53e5d63b0f18b8d09505054d8150ee80" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.434ex; height:2.509ex;" alt="{\displaystyle \alpha \to \beta }"></span> <dl><dd>questa scrittura ci dice che a sinistra ci deve essere almeno un non terminale ed a destra qualsiasi cosa.</dd></dl></li></ol> <div class="mw-heading mw-heading2"><h2 id="Definizione">Definizione</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Grammatica_regolare&veaction=edit&section=2" title="Modifica la sezione Definizione" class="mw-editsection-visualeditor"><span>modifica</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Grammatica_regolare&action=edit&section=2" title="Edit section's source code: Definizione"><span>modifica wikitesto</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Le produzioni di una <i>grammatica regolare</i> sono del tipo: </p> <ul><li>nel caso di <b>lineari sinistre</b> (in inglese <i>left regular grammar</i>)</li></ul> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\to \beta ,A\in N,\beta \in (N\circ \Sigma )\cup \Sigma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo stretchy="false">→</mo> <mi>β</mi> <mo>,</mo> <mi>A</mi> <mo>∈</mo> <mi>N</mi> <mo>,</mo> <mi>β</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mi>N</mi> <mo>∘</mo> <mi mathvariant="normal">Σ</mi> <mo stretchy="false">)</mo> <mo>∪</mo> <mi mathvariant="normal">Σ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A\to \beta ,A\in N,\beta \in (N\circ \Sigma )\cup \Sigma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fd26303f306cd34c98cfa6117f96c277b4135038" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.583ex; height:2.843ex;" alt="{\displaystyle A\to \beta ,A\in N,\beta \in (N\circ \Sigma )\cup \Sigma }"></span></dd> <dd>ossia a sinistra della regola di produzione c'è un non terminale e a destra un non terminale seguito da un terminale oppure un singolo terminale.</dd></dl> <ul><li>nel caso di <b>lineari destre</b> (in inglese <i>right regular grammar</i>)</li></ul> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\to \beta ,A\in N,\beta \in (\Sigma \circ N)\cup \Sigma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo stretchy="false">→</mo> <mi>β</mi> <mo>,</mo> <mi>A</mi> <mo>∈</mo> <mi>N</mi> <mo>,</mo> <mi>β</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mi mathvariant="normal">Σ</mi> <mo>∘</mo> <mi>N</mi> <mo stretchy="false">)</mo> <mo>∪</mo> <mi mathvariant="normal">Σ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A\to \beta ,A\in N,\beta \in (\Sigma \circ N)\cup \Sigma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d06f88a19bc201476205127ae20ee7eb4771aeea" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.583ex; height:2.843ex;" alt="{\displaystyle A\to \beta ,A\in N,\beta \in (\Sigma \circ N)\cup \Sigma }"></span></dd> <dd>ossia a sinistra della regola di produzione c'è un non terminale e a destra un terminale seguito da un non terminale oppure un singolo terminale.</dd></dl> <p>Poniamo attenzione al fatto che non ci devono essere produzioni miste formate da lineari destre e sinistre contemporaneamente nella stessa grammatica, poiché in questo caso non siamo più in presenza di una grammatica regolare ma ad una <a href="/wiki/Grammatica_libera_dal_contesto" title="Grammatica libera dal contesto">grammatica libera dal contesto</a> (<i>non contestuale</i>) come evidenziato in un esempio seguente. </p><p>Vengono chiamate <i>regolari</i> perché i linguaggi generati da queste grammatiche sono rappresentabili tramite <a href="/wiki/Espressione_regolare" title="Espressione regolare">espressioni regolari</a>.<br /> Il termine <i>lineare</i> deriva dal fatto che a destra delle produzioni possiamo trovare al massimo un non terminale; <i>destra</i> o <i>sinistra</i> indica dove il non terminale sarà rispetto al terminale. </p><p>I linguaggi generabili da grammatiche regolari (di tipo-3) sono detti <a href="/wiki/Linguaggio_regolare" title="Linguaggio regolare">linguaggi regolari</a> e sono equivalenti ai linguaggi riconosciuti dagli <a href="/wiki/Automa_a_stati_finiti" title="Automa a stati finiti">automi a stati finiti</a> ed ai linguaggi rappresentati da <a href="/wiki/Espressione_regolare" title="Espressione regolare">espressioni regolari</a>. </p><p>Ogni grammatica regolare è anche una <a href="/wiki/Grammatica_libera_dal_contesto" title="Grammatica libera dal contesto">grammatica libera dal contesto</a> visto che le grammatiche tipo-3 sono strettamente contenute in quelle tipo-2 secondo la <a href="/wiki/Gerarchia_di_Chomsky" title="Gerarchia di Chomsky">gerarchia di Chomsky</a>. </p><p>Alcuni libri di testo e articoli non ammettono regole di produzione vuote (<i>ε-produzioni</i>), e assumono che la stringa vuota non sia presente nel linguaggio.<br /> Ad ogni modo è dimostrato il teorema che garantisce che data una grammatica <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {G}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">G</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {G}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a980c59d42c003fd07fdf3646e1fb95ff82f99" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.392ex; height:2.343ex;" alt="{\displaystyle {\mathcal {G}}}"></span> le cui regole di produzione P possono essere separate in due sottoinsiemi contenenti uno le produzioni vuote e l'altro le produzioni di tipo regolare, allora esiste una grammatica regolare <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {G}}'}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">G</mi> </mrow> </mrow> <mo>′</mo> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {G}}'}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06fb5ae456f801f6965708881255344eed20178c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.08ex; height:2.676ex;" alt="{\displaystyle {\mathcal {G}}'}"></span> formata dalla grammatica <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {G}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">G</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {G}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a980c59d42c003fd07fdf3646e1fb95ff82f99" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.392ex; height:2.343ex;" alt="{\displaystyle {\mathcal {G}}}"></span> a cui sono state eliminate le produzioni vuote.<br /> Più formalmente <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {G}}'}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">G</mi> </mrow> </mrow> <mo>′</mo> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {G}}'}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06fb5ae456f801f6965708881255344eed20178c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.08ex; height:2.676ex;" alt="{\displaystyle {\mathcal {G}}'}"></span> regolare senza ε-produzioni tale che <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L({\mathcal {G}}')=L({\mathcal {G}})-\{\varepsilon \}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mo stretchy="false">(</mo> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">G</mi> </mrow> </mrow> <mo>′</mo> </msup> <mo stretchy="false">)</mo> <mo>=</mo> <mi>L</mi> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">G</mi> </mrow> </mrow> <mo stretchy="false">)</mo> <mo>−</mo> <mo fence="false" stretchy="false">{</mo> <mi>ε</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L({\mathcal {G}}')=L({\mathcal {G}})-\{\varepsilon \}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/96e5324f9f7c41156d6f9adc7961e19830f3ee76" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.604ex; height:3.009ex;" alt="{\displaystyle L({\mathcal {G}}')=L({\mathcal {G}})-\{\varepsilon \}}"></span> </p> <div class="mw-heading mw-heading2"><h2 id="Esempi">Esempi</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Grammatica_regolare&veaction=edit&section=3" title="Modifica la sezione Esempi" class="mw-editsection-visualeditor"><span>modifica</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Grammatica_regolare&action=edit&section=3" title="Edit section's source code: Esempi"><span>modifica wikitesto</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Un esempio di grammatica lineare destra <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {G}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">G</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {G}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a980c59d42c003fd07fdf3646e1fb95ff82f99" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.392ex; height:2.343ex;" alt="{\displaystyle {\mathcal {G}}}"></span> con <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=\{S\},\Sigma =\{a,b\},S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>S</mi> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mi mathvariant="normal">Σ</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=\{S\},\Sigma =\{a,b\},S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/14280aeed17ec46ee5350c11a413f055ebdfc7e8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.916ex; height:2.843ex;" alt="{\displaystyle N=\{S\},\Sigma =\{a,b\},S}"></span> assioma, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}"></span> formato dalle seguenti regole di produzione: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\to aS}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo stretchy="false">→</mo> <mi>a</mi> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S\to aS}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6cca6db86a18a7bd32e3606466e9456c6f90ef45" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.842ex; height:2.176ex;" alt="{\displaystyle S\to aS}"></span></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\to b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo stretchy="false">→</mo> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S\to b}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb47979966e648e11c19beca13c6321365d4610b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.111ex; height:2.176ex;" alt="{\displaystyle S\to b}"></span></dd></dl> <p>Questa grammatica descrive lo stesso linguaggio dell'<a href="/wiki/Espressione_regolare" title="Espressione regolare">espressione regolare</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{*}b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a^{*}b}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c724d8c5c8309846534b801f1a136021ce9c4239" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.282ex; height:2.343ex;" alt="{\displaystyle a^{*}b}"></span>. </p><p>Un altro esempio di grammatica lineare destra <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {G}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">G</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {G}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a980c59d42c003fd07fdf3646e1fb95ff82f99" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.392ex; height:2.343ex;" alt="{\displaystyle {\mathcal {G}}}"></span> con <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=\{S,C\},\Sigma =\{a,b,c\},S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>S</mi> <mo>,</mo> <mi>C</mi> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mi mathvariant="normal">Σ</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo>,</mo> <mi>c</mi> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=\{S,C\},\Sigma =\{a,b,c\},S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/89982b7d040caa34bc53b8c4388c20f76e607cc8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.757ex; height:2.843ex;" alt="{\displaystyle N=\{S,C\},\Sigma =\{a,b,c\},S}"></span> assioma, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}"></span> formato dalle seguenti regole di produzione: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\to aS}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo stretchy="false">→</mo> <mi>a</mi> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S\to aS}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6cca6db86a18a7bd32e3606466e9456c6f90ef45" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.842ex; height:2.176ex;" alt="{\displaystyle S\to aS}"></span></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\to bC}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo stretchy="false">→</mo> <mi>b</mi> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S\to bC}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e90635e27fab95545746390fe4d8e308a207e265" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.877ex; height:2.176ex;" alt="{\displaystyle S\to bC}"></span></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\to b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo stretchy="false">→</mo> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S\to b}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb47979966e648e11c19beca13c6321365d4610b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.111ex; height:2.176ex;" alt="{\displaystyle S\to b}"></span></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\to cC}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mo stretchy="false">→</mo> <mi>c</mi> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C\to cC}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1dfcc1109f3dc31920486ea85b46c063452cf09a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.154ex; height:2.176ex;" alt="{\displaystyle C\to cC}"></span></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\to c}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mo stretchy="false">→</mo> <mi>c</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C\to c}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b397983ceee5694a4daa59ff269a4168d4403afe" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.387ex; height:2.176ex;" alt="{\displaystyle C\to c}"></span></dd></dl> <p>Questa grammatica descrive lo stesso linguaggio dell'<a href="/wiki/Espressione_regolare" title="Espressione regolare">espressione regolare</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a*bc*}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>∗</mo> <mi>b</mi> <mi>c</mi> <mo>∗</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a*bc*}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d4958a65b4c27f6bba07662cbbf78d53677f46a6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.591ex; height:2.176ex;" alt="{\displaystyle a*bc*}"></span>. </p> <div class="mw-heading mw-heading3"><h3 id="Esempio_di_grammatica_non_regolare">Esempio di grammatica non regolare</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Grammatica_regolare&veaction=edit&section=4" title="Modifica la sezione Esempio di grammatica non regolare" class="mw-editsection-visualeditor"><span>modifica</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Grammatica_regolare&action=edit&section=4" title="Edit section's source code: Esempio di grammatica non regolare"><span>modifica wikitesto</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Una grammatica che genera il linguaggio <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L=\{a^{i}b^{i}\;|\;i\geq 0\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> <msup> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> <mspace width="thickmathspace" /> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mspace width="thickmathspace" /> <mi>i</mi> <mo>≥</mo> <mn>0</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L=\{a^{i}b^{i}\;|\;i\geq 0\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0ecf31ba080dd9f798f07ad53437cbfa1c7b009f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.833ex; height:3.176ex;" alt="{\displaystyle L=\{a^{i}b^{i}\;|\;i\geq 0\}}"></span> può essere <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {G}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">G</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {G}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a980c59d42c003fd07fdf3646e1fb95ff82f99" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.392ex; height:2.343ex;" alt="{\displaystyle {\mathcal {G}}}"></span> con <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=\{S,A\},\Sigma =\{a,b\},S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>S</mi> <mo>,</mo> <mi>A</mi> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mi mathvariant="normal">Σ</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=\{S,A\},\Sigma =\{a,b\},S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4d497ab61254b13d2543923be741d766c95d2a81" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.693ex; height:2.843ex;" alt="{\displaystyle N=\{S,A\},\Sigma =\{a,b\},S}"></span> assioma, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}"></span> formato dalle seguenti regole di produzione: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\to aA}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo stretchy="false">→</mo> <mi>a</mi> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S\to aA}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3fa70ce78d5da41357a4da2382ed86167f35b9e3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.086ex; height:2.176ex;" alt="{\displaystyle S\to aA}"></span></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\to Sb}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo stretchy="false">→</mo> <mi>S</mi> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A\to Sb}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/12b949b555ff40476dd91768608c11adfbd146e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.854ex; height:2.176ex;" alt="{\displaystyle A\to Sb}"></span></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\to \varepsilon }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> <mo stretchy="false">→</mo> <mi>ε</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S\to \varepsilon }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eb30bc1a4b59dcdeb095ecfaad991c8e3b0d26c8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.197ex; height:2.176ex;" alt="{\displaystyle S\to \varepsilon }"></span></dd></dl> <p>ma questa non è una grammatica regolare bensì una <a href="/wiki/Grammatica_libera_dal_contesto" title="Grammatica libera dal contesto">grammatica libera dal contesto</a>; ha <i>entrambe</i> le produzioni, destre e sinistre, e quindi non è regolare. </p> <div class="mw-heading mw-heading2"><h2 id="Bibliografia">Bibliografia</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Grammatica_regolare&veaction=edit&section=5" title="Modifica la sezione Bibliografia" class="mw-editsection-visualeditor"><span>modifica</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Grammatica_regolare&action=edit&section=5" title="Edit section's source code: Bibliografia"><span>modifica wikitesto</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>Giorgio Ausiello, Fabrizio d'Amore, Giorgio Gambosi. <i>Linguaggi, Modelli, Complessità</i>. Franco Angeli Editore, 2003 <a href="/wiki/Speciale:RicercaISBN/8846444701" class="internal mw-magiclink-isbn">ISBN 88-464-4470-1</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Voci_correlate">Voci correlate</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Grammatica_regolare&veaction=edit&section=6" title="Modifica la sezione Voci correlate" class="mw-editsection-visualeditor"><span>modifica</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Grammatica_regolare&action=edit&section=6" title="Edit section's source code: Voci correlate"><span>modifica wikitesto</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Linguaggio_regolare" title="Linguaggio regolare">Linguaggio regolare</a></li> <li><a href="/wiki/Automa_a_stati_finiti" title="Automa a stati finiti">Automa a stati finiti</a></li> <li><a href="/wiki/Espressione_regolare" title="Espressione regolare">Espressione regolare</a></li></ul> <ul><li><a href="/wiki/Grammatica_lineare" title="Grammatica lineare">Grammatica lineare</a> e <a href="/wiki/Linguaggio_lineare" title="Linguaggio lineare">linguaggio lineare</a></li></ul> <table border="0" cellpadding="2" cellspacing="0" class="noprint toccolours" style="margin:0 auto"> <tbody><tr> <th colspan="4" style="background:#ddd;"><a href="/wiki/Automa_(informatica)" title="Automa (informatica)">Teoria degli automi</a>: <a href="/wiki/Linguaggi_formali" class="mw-redirect" title="Linguaggi formali">linguaggi formali</a> e <a href="/wiki/Grammatica_formale" title="Grammatica formale">grammatiche formali</a> </th></tr> <tr align="left"> <th style="border-bottom:2px solid"><b><a href="/wiki/Gerarchia_di_Chomsky" title="Gerarchia di Chomsky">Gerarchia di Chomsky</a></b> </th> <th style="border-bottom:2px solid"><b><a href="/wiki/Grammatica_formale" title="Grammatica formale">Grammatica formale</a></b> </th> <th style="border-bottom:2px solid"><b><a href="/wiki/Linguaggio_formale" title="Linguaggio formale">Linguaggio</a></b> </th> <th style="border-bottom:2px solid"><b><a href="/wiki/Automa_(informatica)" title="Automa (informatica)">Automa</a> minimo</b> </th></tr> <tr align="left"> <td>Tipo-0 </td> <td>(illimitato) </td> <td><a href="/wiki/Linguaggio_ricorsivamente_enumerabile" title="Linguaggio ricorsivamente enumerabile">Ricorsivamente enumerabile</a> </td> <td><a href="/wiki/Macchina_di_Turing" title="Macchina di Turing">Macchina di Turing</a> </td></tr> <tr align="left"> <td> </td> <td>(illimitato) </td> <td><a href="/wiki/Linguaggio_ricorsivo" title="Linguaggio ricorsivo">Ricorsivo</a> </td> <td><a href="/wiki/Macchina_che_termina_sempre" title="Macchina che termina sempre">Decider</a> </td></tr> <tr align="left"> <td>Tipo-1 </td> <td><a href="/wiki/Grammatica_dipendente_dal_contesto" title="Grammatica dipendente dal contesto">Dipendente dal contesto</a> </td> <td><a href="/wiki/Linguaggio_dipendente_dal_contesto" title="Linguaggio dipendente dal contesto">Dipendente dal contesto</a> </td> <td><a href="/wiki/Automa_lineare_limitato" title="Automa lineare limitato">Automa lineare</a> </td></tr> <tr align="left"> <td>Tipo-2 </td> <td><a href="/wiki/Grammatica_libera_dal_contesto" title="Grammatica libera dal contesto">Libera dal contesto</a> </td> <td><a href="/wiki/Linguaggio_libero_dal_contesto" title="Linguaggio libero dal contesto">Libero dal contesto</a> </td> <td><a href="/wiki/Automa_a_pila" title="Automa a pila">Automa a pila ND</a> </td></tr> <tr align="left"> <td>Tipo-3 </td> <td><a class="mw-selflink selflink">Regolare</a> </td> <td><a href="/wiki/Linguaggio_regolare" title="Linguaggio regolare">Regolare</a> </td> <td><a href="/wiki/Automa_a_stati_finiti" title="Automa a stati finiti">A stati finiti</a> </td></tr> <tr> <th style="border-top:2px solid" colspan="4"><small>Ciascuna categoria di linguaggio o grammatica è un <a href="/wiki/Sottoinsieme_proprio" class="mw-redirect" title="Sottoinsieme proprio">sottoinsieme proprio</a> della categoria immediatamente sovrastante.</small> </th></tr> </tbody></table> <div class="noprint" style="width:100%; padding: 3px 0; display: flex; flex-wrap: wrap; row-gap: 4px; column-gap: 8px; box-sizing: border-box;"><div style="flex-basis: calc( 100% / 2 - 8px / 2 );"><style data-mw-deduplicate="TemplateStyles:r140555418">.mw-parser-output .itwiki-template-occhiello{width:100%;line-height:25px;border:1px solid #CCF;background-color:#F0EEFF;box-sizing:border-box}.mw-parser-output .itwiki-template-occhiello-progetto{background-color:#FAFAFA}@media screen{html.skin-theme-clientpref-night .mw-parser-output .itwiki-template-occhiello{background-color:#202122;border-color:#54595D}html.skin-theme-clientpref-night .mw-parser-output .itwiki-template-occhiello-progetto{background-color:#282929}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .itwiki-template-occhiello{background-color:#202122;border-color:#54595D}html.skin-theme-clientpref-os .mw-parser-output .itwiki-template-occhiello-progetto{background-color:#282929}}</style><div class="itwiki-template-occhiello"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Computer_n_screen.svg" class="mw-file-description" title="Informatica"><img alt=" " src="//upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png" decoding="async" width="24" height="25" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/37px-Computer_n_screen.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/48px-Computer_n_screen.svg.png 2x" data-file-width="119" data-file-height="123" /></a></span> <b><a href="/wiki/Portale:Informatica" title="Portale:Informatica">Portale Informatica</a></b></div></div><div style="flex-basis: calc( 100% / 2 - 8px / 2 );"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r140555418"><div class="itwiki-template-occhiello"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Crystal128-kanagram.svg" class="mw-file-description" title="Linguistica"><img alt=" " src="//upload.wikimedia.org/wikipedia/commons/thumb/0/0d/Crystal128-kanagram.svg/25px-Crystal128-kanagram.svg.png" decoding="async" width="25" height="25" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/0/0d/Crystal128-kanagram.svg/38px-Crystal128-kanagram.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/0/0d/Crystal128-kanagram.svg/50px-Crystal128-kanagram.svg.png 2x" data-file-width="256" data-file-height="256" /></a></span> <b><a href="/wiki/Portale:Linguistica" title="Portale:Linguistica">Portale Linguistica</a></b></div></div></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Estratto da "<a dir="ltr" href="https://it.wikipedia.org/w/index.php?title=Grammatica_regolare&oldid=139475211">https://it.wikipedia.org/w/index.php?title=Grammatica_regolare&oldid=139475211</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Categoria:Categorie" title="Categoria:Categorie">Categoria</a>: <ul><li><a href="/wiki/Categoria:Teoria_dei_linguaggi_formali" title="Categoria:Teoria dei linguaggi formali">Teoria dei linguaggi formali</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Categoria nascosta: <ul><li><a href="/wiki/Categoria:Pagine_che_utilizzano_collegamenti_magici_ISBN" title="Categoria:Pagine che utilizzano collegamenti magici ISBN">Pagine che utilizzano collegamenti magici ISBN</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> Questa pagina è stata modificata per l'ultima volta il 26 mag 2024 alle 09:22.</li> <li id="footer-info-copyright">Il testo è disponibile secondo la <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.it">licenza Creative Commons Attribuzione-Condividi allo stesso modo</a>; possono applicarsi condizioni ulteriori. Vedi le <a class="external text" href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use/it">condizioni d'uso</a> per i dettagli.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/it">Informativa sulla privacy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:Sala_stampa/Wikipedia">Informazioni su Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:Avvertenze_generali">Avvertenze</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Codice di condotta</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Sviluppatori</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/it.wikipedia.org">Statistiche</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Dichiarazione sui cookie</a></li> <li id="footer-places-mobileview"><a href="//it.m.wikipedia.org/w/index.php?title=Grammatica_regolare&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Versione mobile</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-6b8d669998-6b5zc","wgBackendResponseTime":158,"wgPageParseReport":{"limitreport":{"cputime":"0.102","walltime":"0.226","ppvisitednodes":{"value":2370,"limit":1000000},"postexpandincludesize":{"value":3826,"limit":2097152},"templateargumentsize":{"value":293,"limit":2097152},"expansiondepth":{"value":9,"limit":100},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":3977,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 80.069 1 -total"," 51.20% 40.994 1 Template:Vedi_anche"," 44.29% 35.463 1 Template:Portale"," 22.88% 18.323 2 Template:Icona_argomento"," 3.13% 2.506 1 Template:Linguaggi_formali_e_grammatiche"]},"scribunto":{"limitreport-timeusage":{"value":"0.043","limit":"10.000"},"limitreport-memusage":{"value":669223,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-745f94f9f8-4bkpv","timestamp":"20241120075418","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Grammatica regolare","url":"https:\/\/it.wikipedia.org\/wiki\/Grammatica_regolare","sameAs":"http:\/\/www.wikidata.org\/entity\/Q645527","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q645527","author":{"@type":"Organization","name":"Contributori ai progetti Wikimedia"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-12-05T16:54:24Z","dateModified":"2024-05-26T08:22:48Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/2\/26\/Gerarchia-di-Chomsky.jpg","headline":"grammatica formale generativa"}</script> </body> </html>