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-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Formal language - 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-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);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":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"5a26e0b4-b3e9-4c1a-bd9e-892ac47f93e3","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Formal_language","wgTitle":"Formal language","wgCurRevisionId":1244534630,"wgRevisionId":1244534630,"wgArticleId":10939,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Articles needing additional references from March 2024","All articles needing additional references","Use dmy dates from November 2023","Articles to be expanded from March 2021","All articles to be expanded","Webarchive template wayback links","Formal languages","Theoretical computer science","Combinatorics on words"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel": "wikitext","wgRelevantPageName":"Formal_language","wgRelevantArticleId":10939,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q192161","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness" ,"fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","ext.scribunto.logs","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP", "ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","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=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.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=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <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/thumb/a/aa/Syntax_tree.svg/1200px-Syntax_tree.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1029"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Syntax_tree.svg/800px-Syntax_tree.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="686"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Syntax_tree.svg/640px-Syntax_tree.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="549"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Formal language - 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="//en.m.wikipedia.org/wiki/Formal_language"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Formal_language&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 (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Formal_language"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&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-Formal_language rootpage-Formal_language skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</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="Site"> <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="Main menu" > <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">Main menu</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">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" 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="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; 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/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</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="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search 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="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <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="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <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="Appearance" > <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">Appearance</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="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</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=Special:CreateAccount&returnto=Formal+language" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</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=Special:UserLogin&returnto=Formal+language" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</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="Log in and more options" > <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="Personal tools" > <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">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <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="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Formal+language" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Formal+language" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</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"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</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/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</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="Site"> <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="Contents" 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">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</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">(Top)</div> </a> </li> <li id="toc-History" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#History"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>History</span> </div> </a> <ul id="toc-History-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Words_over_an_alphabet" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Words_over_an_alphabet"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Words over an alphabet</span> </div> </a> <ul id="toc-Words_over_an_alphabet-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Definition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Definition</span> </div> </a> <ul id="toc-Definition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Examples" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Examples"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Examples</span> </div> </a> <button aria-controls="toc-Examples-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>Toggle Examples subsection</span> </button> <ul id="toc-Examples-sublist" class="vector-toc-list"> <li id="toc-Constructions" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Constructions"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Constructions</span> </div> </a> <ul id="toc-Constructions-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Language-specification_formalisms" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Language-specification_formalisms"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Language-specification formalisms</span> </div> </a> <ul id="toc-Language-specification_formalisms-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Operations_on_languages" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Operations_on_languages"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Operations on languages</span> </div> </a> <ul id="toc-Operations_on_languages-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Applications</span> </div> </a> <button aria-controls="toc-Applications-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>Toggle Applications subsection</span> </button> <ul id="toc-Applications-sublist" class="vector-toc-list"> <li id="toc-Programming_languages" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Programming_languages"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.1</span> <span>Programming languages</span> </div> </a> <ul id="toc-Programming_languages-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Formal_theories,_systems,_and_proofs" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Formal_theories,_systems,_and_proofs"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.2</span> <span>Formal theories, systems, and proofs</span> </div> </a> <ul id="toc-Formal_theories,_systems,_and_proofs-sublist" class="vector-toc-list"> <li id="toc-Interpretations_and_models" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Interpretations_and_models"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.2.1</span> <span>Interpretations and models</span> </div> </a> <ul id="toc-Interpretations_and_models-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>References</span> </div> </a> <button aria-controls="toc-References-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>Toggle References subsection</span> </button> <ul id="toc-References-sublist" class="vector-toc-list"> <li id="toc-Citations" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Citations"> <div class="vector-toc-text"> <span class="vector-toc-numb">10.1</span> <span>Citations</span> </div> </a> <ul id="toc-Citations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Sources" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Sources"> <div class="vector-toc-text"> <span class="vector-toc-numb">10.2</span> <span>Sources</span> </div> </a> <ul id="toc-Sources-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">11</span> <span>External links</span> </div> </a> <ul id="toc-External_links-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="Contents" 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="Toggle the table of contents" > <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">Toggle the table of contents</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">Formal language</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="Go to an article in another language. Available in 51 languages" > <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-51" 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">51 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D9%84%D8%BA%D8%A9_%D9%85%D8%AA%D8%B5%D8%B1%D9%81%D8%A9" title="لغة متصرفة – Arabic" lang="ar" hreflang="ar" data-title="لغة متصرفة" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-az mw-list-item"><a href="https://az.wikipedia.org/wiki/Formal_dill%C9%99r" title="Formal dillər – Azerbaijani" lang="az" hreflang="az" data-title="Formal dillər" data-language-autonym="Azərbaycanca" data-language-local-name="Azerbaijani" class="interlanguage-link-target"><span>Azərbaycanca</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D0%B5%D0%BD_%D0%B5%D0%B7%D0%B8%D0%BA" title="Формален език – Bulgarian" lang="bg" hreflang="bg" data-title="Формален език" data-language-autonym="Български" data-language-local-name="Bulgarian" class="interlanguage-link-target"><span>Български</span></a></li><li class="interlanguage-link interwiki-bs mw-list-item"><a href="https://bs.wikipedia.org/wiki/Formalni_jezik" title="Formalni jezik – Bosnian" lang="bs" hreflang="bs" data-title="Formalni jezik" data-language-autonym="Bosanski" data-language-local-name="Bosnian" class="interlanguage-link-target"><span>Bosanski</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Llenguatge_formal" title="Llenguatge formal – Catalan" lang="ca" hreflang="ca" data-title="Llenguatge formal" data-language-autonym="Català" data-language-local-name="Catalan" 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/Form%C3%A1ln%C3%AD_jazyk" title="Formální jazyk – Czech" lang="cs" hreflang="cs" data-title="Formální jazyk" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Formalsprog" title="Formalsprog – Danish" lang="da" hreflang="da" data-title="Formalsprog" data-language-autonym="Dansk" data-language-local-name="Danish" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Formale_Sprache" title="Formale Sprache – German" lang="de" hreflang="de" data-title="Formale Sprache" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%A4%CF%85%CF%80%CE%B9%CE%BA%CE%AE_%CE%B3%CE%BB%CF%8E%CF%83%CF%83%CE%B1" title="Τυπική γλώσσα – Greek" lang="el" hreflang="el" data-title="Τυπική γλώσσα" data-language-autonym="Ελληνικά" data-language-local-name="Greek" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Lenguaje_formal" title="Lenguaje formal – Spanish" lang="es" hreflang="es" data-title="Lenguaje formal" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Formala_lingvo" title="Formala lingvo – Esperanto" lang="eo" hreflang="eo" data-title="Formala lingvo" data-language-autonym="Esperanto" data-language-local-name="Esperanto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%86%D8%B8%D8%B1%DB%8C%D9%87_%D8%B2%D8%A8%D8%A7%D9%86%E2%80%8C%D9%87%D8%A7" title="نظریه زبان‌ها – Persian" lang="fa" hreflang="fa" data-title="نظریه زبان‌ها" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Langage_formel" title="Langage formel – French" lang="fr" hreflang="fr" data-title="Langage formel" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%ED%98%95%EC%8B%9D_%EC%96%B8%EC%96%B4" title="형식 언어 – Korean" lang="ko" hreflang="ko" data-title="형식 언어" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-hi mw-list-item"><a href="https://hi.wikipedia.org/wiki/%E0%A4%94%E0%A4%AA%E0%A4%9A%E0%A4%BE%E0%A4%B0%E0%A4%BF%E0%A4%95_%E0%A4%AD%E0%A4%BE%E0%A4%B7%E0%A4%BE" title="औपचारिक भाषा – Hindi" lang="hi" hreflang="hi" data-title="औपचारिक भाषा" data-language-autonym="हिन्दी" data-language-local-name="Hindi" class="interlanguage-link-target"><span>हिन्दी</span></a></li><li class="interlanguage-link interwiki-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/Formalni_jezik" title="Formalni jezik – Croatian" lang="hr" hreflang="hr" data-title="Formalni jezik" data-language-autonym="Hrvatski" data-language-local-name="Croatian" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Bahasa_formal" title="Bahasa formal – Indonesian" lang="id" hreflang="id" data-title="Bahasa formal" data-language-autonym="Bahasa Indonesia" data-language-local-name="Indonesian" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Linguaggio_formale" title="Linguaggio formale – Italian" lang="it" hreflang="it" data-title="Linguaggio formale" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A9%D7%A4%D7%94_%D7%A4%D7%95%D7%A8%D7%9E%D7%9C%D7%99%D7%AA" title="שפה פורמלית – Hebrew" lang="he" hreflang="he" data-title="שפה פורמלית" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ht mw-list-item"><a href="https://ht.wikipedia.org/wiki/Langaj_f%C3%B2m%C3%A8l" title="Langaj fòmèl – Haitian Creole" lang="ht" hreflang="ht" data-title="Langaj fòmèl" data-language-autonym="Kreyòl ayisyen" data-language-local-name="Haitian Creole" class="interlanguage-link-target"><span>Kreyòl ayisyen</span></a></li><li class="interlanguage-link interwiki-lt mw-list-item"><a href="https://lt.wikipedia.org/wiki/Formali_kalba" title="Formali kalba – Lithuanian" lang="lt" hreflang="lt" data-title="Formali kalba" data-language-autonym="Lietuvių" data-language-local-name="Lithuanian" class="interlanguage-link-target"><span>Lietuvių</span></a></li><li class="interlanguage-link interwiki-lmo mw-list-item"><a href="https://lmo.wikipedia.org/wiki/Lenguagg_formal" title="Lenguagg formal – Lombard" lang="lmo" hreflang="lmo" data-title="Lenguagg formal" data-language-autonym="Lombard" data-language-local-name="Lombard" class="interlanguage-link-target"><span>Lombard</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/Form%C3%A1lis_nyelv" title="Formális nyelv – Hungarian" lang="hu" hreflang="hu" data-title="Formális nyelv" data-language-autonym="Magyar" data-language-local-name="Hungarian" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-mk mw-list-item"><a href="https://mk.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D0%B5%D0%BD_%D1%98%D0%B0%D0%B7%D0%B8%D0%BA" title="Формален јазик – Macedonian" lang="mk" hreflang="mk" data-title="Формален јазик" data-language-autonym="Македонски" data-language-local-name="Macedonian" class="interlanguage-link-target"><span>Македонски</span></a></li><li class="interlanguage-link interwiki-mwl mw-list-item"><a href="https://mwl.wikipedia.org/wiki/Lenguaige_formal" title="Lenguaige formal – Mirandese" lang="mwl" hreflang="mwl" data-title="Lenguaige formal" 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-my mw-list-item"><a href="https://my.wikipedia.org/wiki/%E1%80%A1%E1%80%9B%E1%80%95%E1%80%BA%E1%80%9E%E1%80%AF%E1%80%B6%E1%80%B8_%E1%80%98%E1%80%AC%E1%80%9E%E1%80%AC%E1%80%85%E1%80%80%E1%80%AC%E1%80%B8" title="အရပ်သုံး ဘာသာစကား – Burmese" lang="my" hreflang="my" data-title="အရပ်သုံး ဘာသာစကား" data-language-autonym="မြန်မာဘာသာ" data-language-local-name="Burmese" class="interlanguage-link-target"><span>မြန်မာဘာသာ</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Formele_taal" title="Formele taal – Dutch" lang="nl" hreflang="nl" data-title="Formele taal" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E5%BD%A2%E5%BC%8F%E8%A8%80%E8%AA%9E" title="形式言語 – Japanese" lang="ja" hreflang="ja" data-title="形式言語" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Formelt_spr%C3%A5k" title="Formelt språk – Norwegian Bokmål" lang="nb" hreflang="nb" data-title="Formelt språk" data-language-autonym="Norsk bokmål" data-language-local-name="Norwegian Bokmål" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-nn mw-list-item"><a href="https://nn.wikipedia.org/wiki/Formelt_spr%C3%A5k" title="Formelt språk – Norwegian Nynorsk" lang="nn" hreflang="nn" data-title="Formelt språk" data-language-autonym="Norsk nynorsk" data-language-local-name="Norwegian Nynorsk" class="interlanguage-link-target"><span>Norsk nynorsk</span></a></li><li class="interlanguage-link interwiki-uz mw-list-item"><a href="https://uz.wikipedia.org/wiki/Rasmiy_til" title="Rasmiy til – Uzbek" lang="uz" hreflang="uz" data-title="Rasmiy til" data-language-autonym="Oʻzbekcha / ўзбекча" data-language-local-name="Uzbek" class="interlanguage-link-target"><span>Oʻzbekcha / ўзбекча</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/J%C4%99zyk_formalny" title="Język formalny – Polish" lang="pl" hreflang="pl" data-title="Język formalny" data-language-autonym="Polski" data-language-local-name="Polish" 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/Linguagem_formal" title="Linguagem formal – Portuguese" lang="pt" hreflang="pt" data-title="Linguagem formal" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Limbaj_formal" title="Limbaj formal – Romanian" lang="ro" hreflang="ro" data-title="Limbaj formal" data-language-autonym="Română" data-language-local-name="Romanian" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA" title="Формальный язык – Russian" lang="ru" hreflang="ru" data-title="Формальный язык" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sq mw-list-item"><a href="https://sq.wikipedia.org/wiki/Gjuha_formale" title="Gjuha formale – Albanian" lang="sq" hreflang="sq" data-title="Gjuha formale" data-language-autonym="Shqip" data-language-local-name="Albanian" class="interlanguage-link-target"><span>Shqip</span></a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Formal_language" title="Formal language – Simple English" lang="en-simple" hreflang="en-simple" data-title="Formal language" data-language-autonym="Simple English" data-language-local-name="Simple English" class="interlanguage-link-target"><span>Simple English</span></a></li><li class="interlanguage-link interwiki-sd mw-list-item"><a href="https://sd.wikipedia.org/wiki/%D8%B1%D9%85%D8%B2%D9%8A%D8%AA" title="رمزيت – Sindhi" lang="sd" hreflang="sd" data-title="رمزيت" data-language-autonym="سنڌي" data-language-local-name="Sindhi" class="interlanguage-link-target"><span>سنڌي</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Form%C3%A1lny_jazyk" title="Formálny jazyk – Slovak" lang="sk" hreflang="sk" data-title="Formálny jazyk" data-language-autonym="Slovenčina" data-language-local-name="Slovak" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-ckb mw-list-item"><a href="https://ckb.wikipedia.org/wiki/%D8%B2%D9%85%D8%A7%D9%86%DB%8C_%D8%B4%DB%8E%D9%88%DB%95%DB%8C%DB%8C" title="زمانی شێوەیی – Central Kurdish" lang="ckb" hreflang="ckb" data-title="زمانی شێوەیی" data-language-autonym="کوردی" data-language-local-name="Central Kurdish" class="interlanguage-link-target"><span>کوردی</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D0%BD%D0%B8_%D1%98%D0%B5%D0%B7%D0%B8%D0%BA" title="Формални језик – Serbian" lang="sr" hreflang="sr" data-title="Формални језик" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Formalni_jezik" title="Formalni jezik – Serbo-Croatian" lang="sh" hreflang="sh" data-title="Formalni jezik" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="Serbo-Croatian" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Formaali_kieli" title="Formaali kieli – Finnish" lang="fi" hreflang="fi" data-title="Formaali kieli" data-language-autonym="Suomi" data-language-local-name="Finnish" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Formellt_spr%C3%A5k" title="Formellt språk – Swedish" lang="sv" hreflang="sv" data-title="Formellt språk" data-language-autonym="Svenska" data-language-local-name="Swedish" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%A0%E0%B8%B2%E0%B8%A9%E0%B8%B2%E0%B8%A3%E0%B8%B9%E0%B8%9B%E0%B8%99%E0%B8%B1%E0%B8%A2" title="ภาษารูปนัย – Thai" lang="th" hreflang="th" data-title="ภาษารูปนัย" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/Bi%C3%A7imsel_dil_kuram%C4%B1" title="Biçimsel dil kuramı – Turkish" lang="tr" hreflang="tr" data-title="Biçimsel dil kuramı" data-language-autonym="Türkçe" data-language-local-name="Turkish" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0_%D0%BC%D0%BE%D0%B2%D0%B0" title="Формальна мова – Ukrainian" lang="uk" hreflang="uk" data-title="Формальна мова" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/Ng%C3%B4n_ng%E1%BB%AF_h%C3%ACnh_th%E1%BB%A9c" title="Ngôn ngữ hình thức – Vietnamese" lang="vi" hreflang="vi" data-title="Ngôn ngữ hình thức" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E5%BD%A2%E5%BC%8F%E8%AA%9E%E8%A8%80" title="形式語言 – Cantonese" lang="yue" hreflang="yue" data-title="形式語言" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%BD%A2%E5%BC%8F%E8%AF%AD%E8%A8%80" title="形式语言 – Chinese" lang="zh" hreflang="zh" data-title="形式语言" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li><li class="interlanguage-link interwiki-zgh mw-list-item"><a href="https://zgh.wikipedia.org/wiki/%E2%B5%9C%E2%B4%B0%E2%B5%8E%E2%B5%99%E2%B5%8D%E2%B4%B0%E2%B5%A2%E2%B5%9C_%E2%B5%9C%E2%B4%B0%E2%B5%8D%E2%B5%96%E2%B4%B0%E2%B5%8F%E2%B5%9C" title="ⵜⴰⵎⵙⵍⴰⵢⵜ ⵜⴰⵍⵖⴰⵏⵜ – Standard Moroccan Tamazight" lang="zgh" hreflang="zgh" data-title="ⵜⴰⵎⵙⵍⴰⵢⵜ ⵜⴰⵍⵖⴰⵏⵜ" data-language-autonym="ⵜⴰⵎⴰⵣⵉⵖⵜ ⵜⴰⵏⴰⵡⴰⵢⵜ" data-language-local-name="Standard Moroccan Tamazight" 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/Q192161#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</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="Namespaces"> <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/Formal_language" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Formal_language" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</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="Change language variant" > <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">English</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="Views"> <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/Formal_language"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Formal_language&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Formal_language&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <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="Tools" > <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">Tools</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">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </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/Formal_language"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Formal_language&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Formal_language&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Formal_language" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Formal_language" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Formal_language&oldid=1244534630" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Formal_language&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Formal_language&id=1244534630&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FFormal_language"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FFormal_language"><span>Download QR code</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"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Formal_language&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Formal_language&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</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 other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Formal_languages" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q192161" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</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="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <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">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</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">From Wikipedia, the free encyclopedia</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="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Sequence of words formed by specific rules</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">This article is about a technical term in mathematics and computer science. For any formal type of language usage, see <a href="/wiki/Literary_language" title="Literary language">Literary language</a>. For studies about natural languages, see <a href="/wiki/Formal_semantics_(natural_language)" title="Formal semantics (natural language)">Formal semantics (natural language)</a>.</div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-More_citations_needed plainlinks metadata ambox ambox-content ambox-Refimprove" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>needs additional citations for <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">verification</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/Formal_language" title="Special:EditPage/Formal language">improve this article</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and removed.<br /><small><span class="plainlinks"><i>Find sources:</i> <a rel="nofollow" class="external text" href="https://www.google.com/search?as_eq=wikipedia&q=%22Formal+language%22">"Formal language"</a> – <a rel="nofollow" class="external text" href="https://www.google.com/search?tbm=nws&q=%22Formal+language%22+-wikipedia&tbs=ar:1">news</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?&q=%22Formal+language%22&tbs=bkt:s&tbm=bks">newspapers</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?tbs=bks:1&q=%22Formal+language%22+-wikipedia">books</a> <b>·</b> <a rel="nofollow" class="external text" href="https://scholar.google.com/scholar?q=%22Formal+language%22">scholar</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.jstor.org/action/doBasicSearch?Query=%22Formal+language%22&acc=on&wc=on">JSTOR</a></span></small></span> <span class="date-container"><i>(<span class="date">March 2024</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1246091330">.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}</style><table class="sidebar sidebar-collapse nomobile nowraplinks hlist"><tbody><tr><td class="sidebar-pretitle">Part of <a href="/wiki/Category:Formal_languages" title="Category:Formal languages"><i>a series</i></a> on</td></tr><tr><th class="sidebar-title-with-pretitle"><a href="/wiki/Formal_languages" class="mw-redirect" title="Formal languages">Formal languages</a></th></tr><tr><td class="sidebar-content" style="padding-top:0.2em;"> <div class="sidebar-list mw-collapsible"><div class="sidebar-list-title" style="background:#ddddff;text-align:center;;color: var(--color-base)"><div class="sidebar-list-title-c">Key concepts</div></div><div class="sidebar-list-content mw-collapsible-content"> <ul><li><a href="/wiki/Formal_system" title="Formal system">Formal system</a></li> <li><a href="/wiki/Alphabet_(formal_languages)" title="Alphabet (formal languages)">Alphabet</a></li> <li><a href="/wiki/Syntax_(logic)" title="Syntax (logic)">Syntax</a></li> <li><a href="/wiki/Semantics_of_logic" title="Semantics of logic">Semantics (logic)</a></li> <li><a href="/wiki/Semantics_(computer_science)" title="Semantics (computer science)">Semantics (programming languages)</a></li> <li><a href="/wiki/Formal_grammar" title="Formal grammar">Formal grammar</a></li> <li><a href="/wiki/Formation_rule" title="Formation rule">Formation rule</a></li> <li><a href="/wiki/Well-formed_formula" title="Well-formed formula">Well-formed formula</a></li> <li><a href="/wiki/Automata_theory" title="Automata theory">Automata theory</a></li> <li><a href="/wiki/Regular_expression" title="Regular expression">Regular expression</a></li> <li><a href="/wiki/Production_(computer_science)" title="Production (computer science)">Production</a></li> <li><a href="/wiki/Ground_expression" title="Ground expression">Ground expression</a></li> <li><a href="/wiki/Atomic_formula" title="Atomic formula">Atomic formula</a></li></ul></div></div></td> </tr><tr><td class="sidebar-content" style="padding-top:0.2em;"> <div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="background:#ddddff;text-align:center;;color: var(--color-base)"><div class="sidebar-list-title-c">Applications</div></div><div class="sidebar-list-content mw-collapsible-content"> <ul><li><a href="/wiki/Formal_methods" title="Formal methods">Formal methods</a></li> <li><a href="/wiki/Propositional_calculus" title="Propositional calculus">Propositional calculus</a></li> <li><a href="/wiki/Predicate_logic" class="mw-redirect" title="Predicate logic">Predicate logic</a></li> <li><a href="/wiki/Mathematical_notation" title="Mathematical notation">Mathematical notation</a></li> <li><a href="/wiki/Natural_language_processing" title="Natural language processing">Natural language processing</a></li> <li><a href="/wiki/Programming_language_theory" title="Programming language theory">Programming language theory</a></li> <li><a href="/wiki/Computational_linguistics" title="Computational linguistics">Computational linguistics</a></li> <li><a href="/wiki/Syntax_analysis" class="mw-redirect" title="Syntax analysis">Syntax analysis</a></li> <li><a href="/wiki/Formal_verification" title="Formal verification">Formal verification</a></li> <li><a href="/wiki/Automated_theorem_proving" title="Automated theorem proving">Automated theorem proving</a></li></ul></div></div></td> </tr><tr><td class="sidebar-navbar"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Formal_languages" title="Template:Formal languages"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/w/index.php?title=Template_talk:Formal_languages&action=edit&redlink=1" class="new" title="Template talk:Formal languages (page does not exist)"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Formal_languages" title="Special:EditPage/Template:Formal languages"><abbr title="Edit this template">e</abbr></a></li></ul></div></td></tr></tbody></table> <p class="mw-empty-elt"> </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Syntax_tree.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Syntax_tree.svg/250px-Syntax_tree.svg.png" decoding="async" width="250" height="214" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Syntax_tree.svg/375px-Syntax_tree.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Syntax_tree.svg/500px-Syntax_tree.svg.png 2x" data-file-width="756" data-file-height="648" /></a><figcaption>Structure of the syntactically well-formed, although thoroughly nonsensical, English sentence, <i>"Colorless green ideas sleep furiously"</i> (<a href="/wiki/Colorless_green_ideas_sleep_furiously" title="Colorless green ideas sleep furiously">historical example</a> from <a href="/wiki/Chomsky" class="mw-redirect" title="Chomsky">Chomsky</a> 1957)</figcaption></figure> <p>In <a href="/wiki/Logic" title="Logic">logic</a>, <a href="/wiki/Mathematics" title="Mathematics">mathematics</a>, <a href="/wiki/Computer_science" title="Computer science">computer science</a>, and <a href="/wiki/Linguistics" title="Linguistics">linguistics</a>, a <b>formal language</b> consists of <a href="/wiki/Word" title="Word">words</a> whose <a href="/wiki/Symbol_(formal)" title="Symbol (formal)">letters</a> are taken from an <a href="/wiki/Alphabet_(formal_languages)" title="Alphabet (formal languages)">alphabet</a> and are <a href="/wiki/Well-formedness" title="Well-formedness">well-formed</a> according to a specific set of rules called a <a href="/wiki/Formal_grammar" title="Formal grammar">formal grammar</a>. </p><p>The alphabet of a formal language consists of symbols, letters, or <a href="/wiki/Type%E2%80%93token_distinction" title="Type–token distinction">tokens</a> that concatenate into <a href="/wiki/String_(computer_science)" title="String (computer science)">strings</a> called words.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Words that belong to a particular formal language are sometimes called <i>well-formed words</i> or <i><a href="/wiki/Well-formed_formula" title="Well-formed formula">well-formed formulas</a></i>. A formal language is often defined by means of a <a href="/wiki/Formal_grammar" title="Formal grammar">formal grammar</a> such as a <a href="/wiki/Regular_grammar" title="Regular grammar">regular grammar</a> or <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammar</a>, which consists of its <a href="/wiki/Formation_rule" title="Formation rule">formation rules</a>. </p><p>In computer science, formal languages are used, among others, as the basis for defining the grammar of <a href="/wiki/Programming_language" title="Programming language">programming languages</a> and formalized versions of subsets of natural languages, in which the words of the language represent concepts that are associated with meanings or <a href="/wiki/Semantics" title="Semantics">semantics</a>. In <a href="/wiki/Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, <a href="/wiki/Decision_problem" title="Decision problem">decision problems</a> are typically defined as formal languages, and <a href="/wiki/Complexity_class" title="Complexity class">complexity classes</a> are defined as the sets of the formal languages that can be <a href="/wiki/Parsing" title="Parsing">parsed by machines</a> with limited computational power. In <a href="/wiki/Logic" title="Logic">logic</a> and the <a href="/wiki/Foundations_of_mathematics" title="Foundations of mathematics">foundations of mathematics</a>, formal languages are used to represent the syntax of <a href="/wiki/Axiomatic_system" title="Axiomatic system">axiomatic systems</a>, and <a href="/wiki/Formalism_(philosophy_of_mathematics)" title="Formalism (philosophy of mathematics)">mathematical formalism</a> is the philosophy that all of mathematics can be reduced to the syntactic manipulation of formal languages in this way. </p><p>The field of <b>formal language theory</b> studies primarily the purely <a href="/wiki/Syntactic" class="mw-redirect" title="Syntactic">syntactic</a> aspects of such languages—that is, their internal structural patterns. Formal language theory sprang out of linguistics, as a way of understanding the syntactic regularities of <a href="/wiki/Natural_language" title="Natural language">natural languages</a>. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="History">History</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=1" title="Edit section: History"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Expand_section plainlinks metadata ambox mbox-small-left ambox-content" role="presentation"><tbody><tr><td class="mbox-image"><span typeof="mw:File"><a href="/wiki/File:Wiki_letter_w_cropped.svg" class="mw-file-description"><img alt="[icon]" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png" decoding="async" width="20" height="14" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/30px-Wiki_letter_w_cropped.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/40px-Wiki_letter_w_cropped.svg.png 2x" data-file-width="44" data-file-height="31" /></a></span></td><td class="mbox-text"><div class="mbox-text-span">This section <b>needs expansion</b>. You can help by <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Formal_language&action=edit&section=">adding to it</a>. <span class="date-container"><i>(<span class="date">March 2021</span>)</i></span></div></td></tr></tbody></table> <p>In the 17th century, <a href="/wiki/Gottfried_Leibniz" class="mw-redirect" title="Gottfried Leibniz">Gottfried Leibniz</a> imagined and described the <a href="/wiki/Characteristica_universalis" title="Characteristica universalis">characteristica universalis</a>, a universal and formal language which utilised <a href="/wiki/Pictographs" class="mw-redirect" title="Pictographs">pictographs</a>. Later, <a href="/wiki/Carl_Friedrich_Gauss" title="Carl Friedrich Gauss">Carl Friedrich Gauss</a> investigated the problem of <a href="/wiki/Gauss_notation" title="Gauss notation">Gauss codes</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p><p><a href="/wiki/Gottlob_Frege" title="Gottlob Frege">Gottlob Frege</a> attempted to realize Leibniz's ideas, through a notational system first outlined in <i><a href="/wiki/Begriffsschrift" title="Begriffsschrift">Begriffsschrift</a></i> (1879) and more fully developed in his 2-volume Grundgesetze der Arithmetik (1893/1903).<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> This described a "formal language of pure language."<sup id="cite_ref-Herken1279_4-0" class="reference"><a href="#cite_note-Herken1279-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p><p>In the first half of the 20th century, several developments were made with relevance to formal languages. <a href="/wiki/Axel_Thue" title="Axel Thue">Axel Thue</a> published four papers relating to words and language between 1906 and 1914. The last of these introduced what <a href="/wiki/Emil_Post" class="mw-redirect" title="Emil Post">Emil Post</a> later termed 'Thue Systems', and gave an early example of an <a href="/wiki/Undecidable_problem" title="Undecidable problem">undecidable problem</a>.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> Post would later use this paper as the basis for a 1947 proof "that the word problem for semigroups was recursively insoluble",<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> and later devised the <a href="/wiki/Post_canonical_system" title="Post canonical system">canonical system</a> for the creation of formal languages. </p><p>In 1907, <a href="/wiki/Leonardo_Torres_Quevedo" title="Leonardo Torres Quevedo">Leonardo Torres Quevedo</a> introduced a formal language for the description of mechanical drawings (mechanical devices), in <a href="/wiki/Vienna" title="Vienna">Vienna</a>. He published "Sobre un sistema de notaciones y símbolos destinados a facilitar la descripción de las máquinas" ("On a system of notations and symbols intended to facilitate the description of machines").<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Heinz_Zemanek" title="Heinz Zemanek">Heinz Zemanek</a> rated it as an equivalent to a <a href="/wiki/Programming_language" title="Programming language">programming language</a> for the numerical control of machine tools.<sup id="cite_ref-Bruderer_8-0" class="reference"><a href="#cite_note-Bruderer-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p><p><a href="/wiki/Noam_Chomsky" title="Noam Chomsky">Noam Chomsky</a> devised an abstract representation of formal and natural languages, known as the <a href="/wiki/Chomsky_hierarchy" title="Chomsky hierarchy">Chomsky hierarchy</a>.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> In 1959 <a href="/wiki/John_Backus" title="John Backus">John Backus</a> developed the Backus-Naur form to describe the syntax of a high level programming language, following his work in the creation of <a href="/wiki/FORTRAN" class="mw-redirect" title="FORTRAN">FORTRAN</a>.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Peter_Naur" title="Peter Naur">Peter Naur</a> was the secretary/editor for the ALGOL60 Report in which he used <a href="/wiki/Backus%E2%80%93Naur_form" title="Backus–Naur form">Backus–Naur form</a> to describe the Formal part of ALGOL60. </p> <div class="mw-heading mw-heading2"><h2 id="Words_over_an_alphabet">Words over an alphabet</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=2" title="Edit section: Words over an alphabet"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>An <i>alphabet</i>, in the context of formal languages, can be any <a href="/wiki/Set_(mathematics)" title="Set (mathematics)">set</a>; its elements are called <i>letters</i>. An alphabet may contain an <a href="/wiki/Countable_set" title="Countable set">infinite</a> number of elements;<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>note 1<span class="cite-bracket">]</span></a></sup> however, most definitions in formal language theory specify alphabets with a finite number of elements, and many results apply only to them. It often makes sense to use an <a href="/wiki/Alphabet" title="Alphabet">alphabet</a> in the usual sense of the word, or more generally any finite <a href="/wiki/Character_encoding" title="Character encoding">character encoding</a> such as <a href="/wiki/ASCII" title="ASCII">ASCII</a> or <a href="/wiki/Unicode" title="Unicode">Unicode</a>. </p><p>A <b>word</b> over an alphabet can be any finite sequence (i.e., <a href="/wiki/String_(computer_science)" title="String (computer science)">string</a>) of letters. The set of all words over an alphabet Σ is usually denoted by Σ<sup>*</sup> (using the <a href="/wiki/Kleene_star" title="Kleene star">Kleene star</a>). The length of a word is the number of letters it is composed of. For any alphabet, there is only one word of length 0, the <i>empty word</i>, which is often denoted by e, ε, λ or even Λ. By <a href="/wiki/Concatenation" title="Concatenation">concatenation</a> one can combine two words to form a new word, whose length is the sum of the lengths of the original words. The result of concatenating a word with the empty word is the original word. </p><p>In some applications, especially in <a href="/wiki/Logic" title="Logic">logic</a>, the alphabet is also known as the <i>vocabulary</i> and words are known as <i>formulas</i> or <i>sentences</i>; this breaks the letter/word metaphor and replaces it by a word/sentence metaphor. </p> <div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=3" title="Edit section: Definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A formal language <i>L</i> over an alphabet Σ is a <a href="/wiki/Subset" title="Subset">subset</a> of Σ<sup>*</sup>, that is, a set of words over that alphabet. Sometimes the sets of words are grouped into expressions, whereas rules and constraints may be formulated for the creation of 'well-formed expressions'. </p><p>In computer science and mathematics, which do not usually deal with <a href="/wiki/Natural_language" title="Natural language">natural languages</a>, the adjective "formal" is often omitted as redundant. </p><p>While formal language theory usually concerns itself with formal languages that are described by some syntactic rules, the actual definition of the concept "formal language" is only as above: a (possibly infinite) set of finite-length strings composed from a given alphabet, no more and no less. In practice, there are many languages that can be described by rules, such as <a href="/wiki/Regular_language" title="Regular language">regular languages</a> or <a href="/wiki/Context-free_language" title="Context-free language">context-free languages</a>. The notion of a <a href="/wiki/Formal_grammar" title="Formal grammar">formal grammar</a> may be closer to the intuitive concept of a "language", one described by syntactic rules. By an abuse of the definition, a particular formal language is often thought of as being accompanied with a formal grammar that describes it. </p> <div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=4" title="Edit section: Examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The following rules describe a formal language <span class="texhtml mvar" style="font-style:italic;">L</span> over the alphabet Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}: </p> <ul><li>Every nonempty string that does not contain "+" or "=" and does not start with "0" is in <span class="texhtml mvar" style="font-style:italic;">L</span>.</li> <li>The string "0" is in <span class="texhtml mvar" style="font-style:italic;">L</span>.</li> <li>A string containing "=" is in <span class="texhtml mvar" style="font-style:italic;">L</span> if and only if there is exactly one "=", and it separates two valid strings of <span class="texhtml mvar" style="font-style:italic;">L</span>.</li> <li>A string containing "+" but not "=" is in <span class="texhtml mvar" style="font-style:italic;">L</span> if and only if every "+" in the string separates two valid strings of <span class="texhtml mvar" style="font-style:italic;">L</span>.</li> <li>No string is in <span class="texhtml mvar" style="font-style:italic;">L</span> other than those implied by the previous rules.</li></ul> <p>Under these rules, the string "23+4=555" is in <span class="texhtml mvar" style="font-style:italic;">L</span>, but the string "=234=+" is not. This formal language expresses <a href="/wiki/Natural_number" title="Natural number">natural numbers</a>, well-formed additions, and well-formed addition equalities, but it expresses only what they look like (their <a href="/wiki/Syntax" title="Syntax">syntax</a>), not what they mean (<a href="/wiki/Semantics" title="Semantics">semantics</a>). For instance, nowhere in these rules is there any indication that "0" means the number zero, "+" means addition, "23+4=555" is false, etc. </p> <div class="mw-heading mw-heading3"><h3 id="Constructions">Constructions</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=5" title="Edit section: Constructions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For finite languages, one can explicitly enumerate all well-formed words. For example, we can describe a language <span class="texhtml mvar" style="font-style:italic;">L</span> as just <span class="texhtml mvar" style="font-style:italic;">L</span> = {a, b, ab, cba}. The <a href="/wiki/Degeneracy_(mathematics)" title="Degeneracy (mathematics)">degenerate</a> case of this construction is the <b>empty language</b>, which contains no words at all (<span class="nounderlines"><span class="texhtml mvar" style="font-style:italic;">L</span> = <a href="/wiki/%E2%88%85" class="mw-redirect" title="∅">∅</a></span>). </p><p>However, even over a finite (non-empty) alphabet such as Σ = {a, b} there are an infinite number of finite-length words that can potentially be expressed: "a", "abb", "ababba", "aaababbbbaab", .... Therefore, formal languages are typically infinite, and describing an infinite formal language is not as simple as writing <i>L</i> = {a, b, ab, cba}. Here are some examples of formal languages: </p> <ul><li><span class="texhtml mvar" style="font-style:italic;">L</span> = Σ<sup>*</sup>, the set of <i>all</i> words over Σ;</li> <li><span class="texhtml mvar" style="font-style:italic;">L</span> = {a}<sup>*</sup> = {a<sup><i>n</i></sup>}, where <i>n</i> ranges over the natural numbers and "a<sup><i>n</i></sup>" means "a" repeated <i>n</i> times (this is the set of words consisting only of the symbol "a");</li> <li>the set of syntactically correct programs in a given programming language (the syntax of which is usually defined by a <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free grammar</a>);</li> <li>the set of inputs upon which a certain <a href="/wiki/Turing_machine" title="Turing machine">Turing machine</a> halts; or</li> <li>the set of maximal strings of <a href="/wiki/Alphanumeric" class="mw-redirect" title="Alphanumeric">alphanumeric</a> <a href="/wiki/ASCII" title="ASCII">ASCII</a> characters on this line, i.e.,<br /> the set {the, set, of, maximal, strings, alphanumeric, ASCII, characters, on, this, line, i, e}.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Language-specification_formalisms">Language-specification formalisms</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=6" title="Edit section: Language-specification formalisms"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Formal languages are used as tools in multiple disciplines. However, formal language theory rarely concerns itself with particular languages (except as examples), but is mainly concerned with the study of various types of formalisms to describe languages. For instance, a language can be given as </p> <ul><li>those strings generated by some <a href="/wiki/Formal_grammar" title="Formal grammar">formal grammar</a>;</li> <li>those strings described or matched by a particular <a href="/wiki/Regular_expression" title="Regular expression">regular expression</a>;</li> <li>those strings accepted by some <a href="/wiki/Automata_theory" title="Automata theory">automaton</a>, such as a <a href="/wiki/Turing_machine" title="Turing machine">Turing machine</a> or <a href="/wiki/Finite-state_automaton" class="mw-redirect" title="Finite-state automaton">finite-state automaton</a>;</li> <li>those strings for which some <a href="/wiki/Decision_procedure" class="mw-redirect" title="Decision procedure">decision procedure</a> (an <a href="/wiki/Algorithm" title="Algorithm">algorithm</a> that asks a sequence of related YES/NO questions) produces the answer YES.</li></ul> <p>Typical questions asked about such formalisms include: </p> <ul><li>What is their expressive power? (Can formalism <i>X</i> describe every language that formalism <i>Y</i> can describe? Can it describe other languages?)</li> <li>What is their recognizability? (How difficult is it to decide whether a given word belongs to a language described by formalism <i>X</i>?)</li> <li>What is their comparability? (How difficult is it to decide whether two languages, one described in formalism <i>X</i> and one in formalism <i>Y</i>, or in <i>X</i> again, are actually the same language?).</li></ul> <p>Surprisingly often, the answer to these decision problems is "it cannot be done at all", or "it is extremely expensive" (with a characterization of how expensive). Therefore, formal language theory is a major application area of <a href="/wiki/Computability_theory" title="Computability theory">computability theory</a> and <a href="/wiki/Computational_complexity_theory" title="Computational complexity theory">complexity theory</a>. Formal languages may be classified in the <a href="/wiki/Chomsky_hierarchy" title="Chomsky hierarchy">Chomsky hierarchy</a> based on the expressive power of their generative grammar as well as the complexity of their recognizing <a href="/wiki/Automata_theory" title="Automata theory">automaton</a>. <a href="/wiki/Context-free_grammar" title="Context-free grammar">Context-free grammars</a> and <a href="/wiki/Regular_grammar" title="Regular grammar">regular grammars</a> provide a good compromise between expressivity and ease of <a href="/wiki/Parsing" title="Parsing">parsing</a>, and are widely used in practical applications. </p> <div class="mw-heading mw-heading2"><h2 id="Operations_on_languages">Operations on languages</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=7" title="Edit section: Operations on languages"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Certain operations on languages are common. This includes the standard set operations, such as union, intersection, and complement. Another class of operation is the element-wise application of string operations. </p><p>Examples: suppose <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_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e79dc1b001f8b923df475ed14de023cbc456013" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{1}}"></span> and <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_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6a952cfe42c86b7741f55a817da0e251793a358" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{2}}"></span> are languages over some common alphabet <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>. </p> <ul><li>The <i><a href="/wiki/Concatenation" title="Concatenation">concatenation</a></i> <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_{1}\cdot L_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>⋅</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}\cdot L_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9baae23a86e910c2912ff231bfacea2bdfe8fc3d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.953ex; height:2.509ex;" alt="{\displaystyle L_{1}\cdot L_{2}}"></span> consists of all strings of the form <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 vw}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> <mi>w</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle vw}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b8354a09980e3eb2de1a7d376cc69b544c43cced" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.792ex; height:1.676ex;" alt="{\displaystyle vw}"></span> where <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 v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}"></span> is a string from <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_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e79dc1b001f8b923df475ed14de023cbc456013" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{1}}"></span> and <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 w}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>w</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle w}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/88b1e0c8e1be5ebe69d18a8010676fa42d7961e6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}"></span> is a string from <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_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6a952cfe42c86b7741f55a817da0e251793a358" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{2}}"></span>.</li> <li>The <i>intersection</i> <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_{1}\cap L_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>∩</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}\cap L_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/159185961cf4ee1f5bcd827ae7efa311b81da905" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.857ex; height:2.509ex;" alt="{\displaystyle L_{1}\cap L_{2}}"></span> of <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_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e79dc1b001f8b923df475ed14de023cbc456013" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{1}}"></span> and <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_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6a952cfe42c86b7741f55a817da0e251793a358" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{2}}"></span> consists of all strings that are contained in both languages</li> <li>The <i>complement</i> <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 \neg L_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">¬</mi> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \neg L_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a24db32a3203c2727ee17874884b0534f0c6dbf4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.187ex; height:2.509ex;" alt="{\displaystyle \neg L_{1}}"></span> of <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_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e79dc1b001f8b923df475ed14de023cbc456013" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{1}}"></span> with respect to <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> consists of all strings over <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> that are not in <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_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e79dc1b001f8b923df475ed14de023cbc456013" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{1}}"></span>.</li> <li>The <a href="/wiki/Kleene_star" title="Kleene star">Kleene star</a>: the language consisting of all words that are concatenations of zero or more words in the original language;</li> <li><i>Reversal</i>: <ul><li>Let <i>ε</i> be the empty word, then <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 \varepsilon ^{R}=\varepsilon }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>ε</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>R</mi> </mrow> </msup> <mo>=</mo> <mi>ε</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varepsilon ^{R}=\varepsilon }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ae758239cc614dcd193d45c4d07f8a48f8cc59ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.745ex; height:2.676ex;" alt="{\displaystyle \varepsilon ^{R}=\varepsilon }"></span>, and</li> <li>for each non-empty word <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 w=\sigma _{1}\cdots \sigma _{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>w</mi> <mo>=</mo> <msub> <mi>σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>⋯</mo> <msub> <mi>σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle w=\sigma _{1}\cdots \sigma _{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/de7c6b87325c73b53b67bc4e43e3657f8c095998" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.187ex; height:2.009ex;" alt="{\displaystyle w=\sigma _{1}\cdots \sigma _{n}}"></span> (where <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 _{1},\ldots ,\sigma _{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \sigma _{1},\ldots ,\sigma _{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3a4aaee3936fcec2bf906c82a25877fea17f119a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.106ex; height:2.009ex;" alt="{\displaystyle \sigma _{1},\ldots ,\sigma _{n}}"></span>are elements of some alphabet), let <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 w^{R}=\sigma _{n}\cdots \sigma _{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>R</mi> </mrow> </msup> <mo>=</mo> <msub> <mi>σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>⋯</mo> <msub> <mi>σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle w^{R}=\sigma _{n}\cdots \sigma _{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0b7dcc7c029f3a3d0970bbf12486cec37c4cc81a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.667ex; height:3.009ex;" alt="{\displaystyle w^{R}=\sigma _{n}\cdots \sigma _{1}}"></span>,</li> <li>then for a formal language <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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}"></span>, <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^{R}=\{w^{R}\mid w\in L\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>R</mi> </mrow> </msup> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <msup> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>R</mi> </mrow> </msup> <mo>∣</mo> <mi>w</mi> <mo>∈</mo> <mi>L</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L^{R}=\{w^{R}\mid w\in L\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/29dc7f79c94b5502cb4de5d615371962e94f5981" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.654ex; height:3.176ex;" alt="{\displaystyle L^{R}=\{w^{R}\mid w\in L\}}"></span>.</li></ul></li> <li><a href="/wiki/String_homomorphism" class="mw-redirect" title="String homomorphism">String homomorphism</a></li></ul> <p>Such <a href="/wiki/String_operations" title="String operations">string operations</a> are used to investigate <a href="/wiki/Closure_(mathematics)" title="Closure (mathematics)">closure properties</a> of classes of languages. A class of languages is closed under a particular operation when the operation, applied to languages in the class, always produces a language in the same class again. For instance, the <a href="/wiki/Context-free_language" title="Context-free language">context-free languages</a> are known to be closed under union, concatenation, and intersection with <a href="/wiki/Regular_language" title="Regular language">regular languages</a>, but not closed under intersection or complement. The theory of <a href="/wiki/Cone_(formal_languages)" title="Cone (formal languages)">trios</a> and <a href="/wiki/Abstract_family_of_languages" title="Abstract family of languages">abstract families of languages</a> studies the most common closure properties of language families in their own right.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </p> <dl><dd><table class="wikitable"> <caption align="top">Closure properties of language families (<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_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e79dc1b001f8b923df475ed14de023cbc456013" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{1}}"></span> Op <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_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6a952cfe42c86b7741f55a817da0e251793a358" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{2}}"></span> where both <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_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e79dc1b001f8b923df475ed14de023cbc456013" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{1}}"></span> and <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_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6a952cfe42c86b7741f55a817da0e251793a358" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.637ex; height:2.509ex;" alt="{\displaystyle L_{2}}"></span> are in the language family given by the column). After Hopcroft and Ullman. </caption> <tbody><tr> <th>Operation </th> <th> </th> <th><a href="/wiki/Regular_language" title="Regular language">Regular</a> </th> <th><a href="/wiki/DCFL" class="mw-redirect" title="DCFL">DCFL</a> </th> <th><a href="/wiki/Context_free_language" class="mw-redirect" title="Context free language">CFL</a> </th> <th><a href="/wiki/Indexed_language" title="Indexed language">IND</a> </th> <th><a href="/wiki/Context_sensitive_language" class="mw-redirect" title="Context sensitive language">CSL</a> </th> <th><a href="/wiki/Recursive_language" title="Recursive language">recursive</a> </th> <th><a href="/wiki/Recursively_enumerable_language" title="Recursively enumerable language">RE</a> </th></tr> <tr> <td><a href="/wiki/Union_(set_theory)" title="Union (set theory)">Union</a> </td> <td><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_{1}\cup L_{2}=\{w\mid w\in L_{1}\lor w\in L_{2}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>∪</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>w</mi> <mo>∣</mo> <mi>w</mi> <mo>∈</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>∨</mo> <mi>w</mi> <mo>∈</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}\cup L_{2}=\{w\mid w\in L_{1}\lor w\in L_{2}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4d257cd807665a3ad81a557ae56717a18377991b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.748ex; height:2.843ex;" alt="{\displaystyle L_{1}\cup L_{2}=\{w\mid w\in L_{1}\lor w\in L_{2}\}}"></span> </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td></tr> <tr> <td><a href="/wiki/Intersection_(set_theory)" title="Intersection (set theory)">Intersection</a> </td> <td><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_{1}\cap L_{2}=\{w\mid w\in L_{1}\land w\in L_{2}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>∩</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>w</mi> <mo>∣</mo> <mi>w</mi> <mo>∈</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>∧</mo> <mi>w</mi> <mo>∈</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}\cap L_{2}=\{w\mid w\in L_{1}\land w\in L_{2}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c0b02a5103fede46a77471ee118c1d44773db792" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.748ex; height:2.843ex;" alt="{\displaystyle L_{1}\cap L_{2}=\{w\mid w\in L_{1}\land w\in L_{2}\}}"></span> </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td></tr> <tr> <td><a href="/wiki/Complement_(set_theory)" title="Complement (set theory)">Complement</a> </td> <td><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 \neg L_{1}=\{w\mid w\not \in L_{1}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">¬</mi> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>w</mi> <mo>∣</mo> <mi>w</mi> <mo>∉</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \neg L_{1}=\{w\mid w\not \in L_{1}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06e6c82f9cceaad96a49f2498d80742132c8b146" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.354ex; height:2.843ex;" alt="{\displaystyle \neg L_{1}=\{w\mid w\not \in L_{1}\}}"></span> </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td></tr> <tr> <td><a href="/wiki/Concatenation" title="Concatenation">Concatenation</a> </td> <td><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_{1}\cdot L_{2}=\{wz\mid w\in L_{1}\land z\in L_{2}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>⋅</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>w</mi> <mi>z</mi> <mo>∣</mo> <mi>w</mi> <mo>∈</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>∧</mo> <mi>z</mi> <mo>∈</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}\cdot L_{2}=\{wz\mid w\in L_{1}\land z\in L_{2}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ce6b5a11ca802fd0abbe846965b1220877682a69" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.356ex; height:2.843ex;" alt="{\displaystyle L_{1}\cdot L_{2}=\{wz\mid w\in L_{1}\land z\in L_{2}\}}"></span> </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td></tr> <tr> <td>Kleene star </td> <td><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_{1}^{*}=\{\varepsilon \}\cup \{wz\mid w\in L_{1}\land z\in L_{1}^{*}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msubsup> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>ε</mi> <mo fence="false" stretchy="false">}</mo> <mo>∪</mo> <mo fence="false" stretchy="false">{</mo> <mi>w</mi> <mi>z</mi> <mo>∣</mo> <mi>w</mi> <mo>∈</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>∧</mo> <mi>z</mi> <mo>∈</mo> <msubsup> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msubsup> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L_{1}^{*}=\{\varepsilon \}\cup \{wz\mid w\in L_{1}\land z\in L_{1}^{*}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c2011c7ac82efd1d10b1edcd52dd627600ba932b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:35.031ex; height:3.009ex;" alt="{\displaystyle L_{1}^{*}=\{\varepsilon \}\cup \{wz\mid w\in L_{1}\land z\in L_{1}^{*}\}}"></span> </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td></tr> <tr> <td>(String) homomorphism <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 h}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>h</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b26be3e694314bc90c3215047e4a2010c6ee184a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}"></span> </td> <td><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 h(L_{1})=\{h(w)\mid w\in L_{1}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>h</mi> <mo stretchy="false">(</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>h</mi> <mo stretchy="false">(</mo> <mi>w</mi> <mo stretchy="false">)</mo> <mo>∣</mo> <mi>w</mi> <mo>∈</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9c76865e5e57da428387eb81fb102b6c6e5e6751" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.1ex; height:2.843ex;" alt="{\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}}"></span> </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td></tr> <tr> <td>ε-free (string) homomorphism <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 h}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>h</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b26be3e694314bc90c3215047e4a2010c6ee184a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}"></span> </td> <td><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 h(L_{1})=\{h(w)\mid w\in L_{1}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>h</mi> <mo stretchy="false">(</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>h</mi> <mo stretchy="false">(</mo> <mi>w</mi> <mo stretchy="false">)</mo> <mo>∣</mo> <mi>w</mi> <mo>∈</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9c76865e5e57da428387eb81fb102b6c6e5e6751" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.1ex; height:2.843ex;" alt="{\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}}"></span> </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td></tr> <tr> <td>Substitution <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 \varphi }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/33ee699558d09cf9d653f6351f9fda0b2f4aaa3e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.52ex; height:2.176ex;" alt="{\displaystyle \varphi }"></span> </td> <td><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 \varphi (L_{1})=\bigcup _{\sigma _{1}\cdots \sigma _{n}\in L_{1}}\varphi (\sigma _{1})\cdot \ldots \cdot \varphi (\sigma _{n})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>φ</mi> <mo stretchy="false">(</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <munder> <mo>⋃</mo> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>⋯</mo> <msub> <mi>σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>∈</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mrow> </munder> <mi>φ</mi> <mo stretchy="false">(</mo> <msub> <mi>σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo>⋅</mo> <mo>…</mo> <mo>⋅</mo> <mi>φ</mi> <mo stretchy="false">(</mo> <msub> <mi>σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \varphi (L_{1})=\bigcup _{\sigma _{1}\cdots \sigma _{n}\in L_{1}}\varphi (\sigma _{1})\cdot \ldots \cdot \varphi (\sigma _{n})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d87d583feb18155c216796a51cd308c247c99a30" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:35.766ex; height:5.843ex;" alt="{\displaystyle \varphi (L_{1})=\bigcup _{\sigma _{1}\cdots \sigma _{n}\in L_{1}}\varphi (\sigma _{1})\cdot \ldots \cdot \varphi (\sigma _{n})}"></span> </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td></tr> <tr> <td>Inverse homomorphism <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 h^{-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>h</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h^{-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8482555dae5cbaa401d8e0cb7d5eb4df203a81b5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.672ex; height:2.676ex;" alt="{\displaystyle h^{-1}}"></span> </td> <td><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 h^{-1}(L_{1})=\bigcup _{w\in L_{1}}h^{-1}(w)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>h</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <munder> <mo>⋃</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>w</mi> <mo>∈</mo> <msub> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mrow> </munder> <msup> <mi>h</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>w</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h^{-1}(L_{1})=\bigcup _{w\in L_{1}}h^{-1}(w)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fa987fc78750adb7034e79cd8186ae7f4ff57cf8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:22.973ex; height:5.843ex;" alt="{\displaystyle h^{-1}(L_{1})=\bigcup _{w\in L_{1}}h^{-1}(w)}"></span> </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td></tr> <tr> <td>Reverse </td> <td><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^{R}=\{w^{R}\mid w\in L\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>L</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>R</mi> </mrow> </msup> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <msup> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>R</mi> </mrow> </msup> <mo>∣</mo> <mi>w</mi> <mo>∈</mo> <mi>L</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L^{R}=\{w^{R}\mid w\in L\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/29dc7f79c94b5502cb4de5d615371962e94f5981" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.654ex; height:3.176ex;" alt="{\displaystyle L^{R}=\{w^{R}\mid w\in L\}}"></span> </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td></tr> <tr> <td>Intersection with a <a href="/wiki/Regular_language" title="Regular language">regular language</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 R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}"></span> </td> <td><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\cap R=\{w\mid w\in L\land w\in R\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mo>∩</mo> <mi>R</mi> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mi>w</mi> <mo>∣</mo> <mi>w</mi> <mo>∈</mo> <mi>L</mi> <mo>∧</mo> <mi>w</mi> <mo>∈</mo> <mi>R</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L\cap R=\{w\mid w\in L\land w\in R\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/10ca0c16bb1008b9c823a7952891c69eb58b50b1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.893ex; height:2.843ex;" alt="{\displaystyle L\cap R=\{w\mid w\in L\land w\in R\}}"></span> </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td> <td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </td></tr></tbody></table></dd></dl> <div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=8" title="Edit section: Applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Programming_languages">Programming languages</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=9" title="Edit section: Programming languages"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main articles: <a href="/wiki/Syntax_(programming_languages)" title="Syntax (programming languages)">Syntax (programming languages)</a> and <a href="/wiki/Compiler-compiler" title="Compiler-compiler">Compiler-compiler</a></div> <p>A compiler usually has two distinct components. A <a href="/wiki/Lexical_analyzer" class="mw-redirect" title="Lexical analyzer">lexical analyzer</a>, sometimes generated by a tool like <a href="/wiki/Lex_programming_tool" class="mw-redirect" title="Lex programming tool"><code>lex</code></a>, identifies the tokens of the programming language grammar, e.g. <a href="/wiki/Identifier" title="Identifier">identifiers</a> or <a href="/wiki/Keyword_(computer_programming)" class="mw-redirect" title="Keyword (computer programming)">keywords</a>, numeric and string literals, punctuation and operator symbols, which are themselves specified by a simpler formal language, usually by means of <a href="/wiki/Regular_expressions" class="mw-redirect" title="Regular expressions">regular expressions</a>. At the most basic conceptual level, a <a href="/wiki/Parser" class="mw-redirect" title="Parser">parser</a>, sometimes generated by a <a href="/wiki/Parser_generator" class="mw-redirect" title="Parser generator">parser generator</a> like <code><a href="/wiki/Yacc" title="Yacc">yacc</a></code>, attempts to decide if the source program is syntactically valid, that is if it is well formed with respect to the programming language grammar for which the compiler was built. </p><p>Of course, compilers do more than just parse the source code – they usually translate it into some executable format. Because of this, a parser usually outputs more than a yes/no answer, typically an <a href="/wiki/Abstract_syntax_tree" title="Abstract syntax tree">abstract syntax tree</a>. This is used by subsequent stages of the compiler to eventually generate an <a href="/wiki/Executable" title="Executable">executable</a> containing <a href="/wiki/Machine_code" title="Machine code">machine code</a> that runs directly on the hardware, or some <a href="/wiki/Intermediate_code" class="mw-redirect" title="Intermediate code">intermediate code</a> that requires a <a href="/wiki/Virtual_machine" title="Virtual machine">virtual machine</a> to execute. </p> <div class="mw-heading mw-heading3"><h3 id="Formal_theories,_systems,_and_proofs"><span id="Formal_theories.2C_systems.2C_and_proofs"></span>Formal theories, systems, and proofs</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=10" title="Edit section: Formal theories, systems, and proofs"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main articles: <a href="/wiki/Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory (mathematical logic)</a> and <a href="/wiki/Formal_system" title="Formal system">Formal system</a></div> <figure class="mw-default-size mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:Formal_languages.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/d/da/Formal_languages.svg/220px-Formal_languages.svg.png" decoding="async" width="220" height="202" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/da/Formal_languages.svg/330px-Formal_languages.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/da/Formal_languages.svg/440px-Formal_languages.svg.png 2x" data-file-width="250" data-file-height="230" /></a><figcaption>This diagram shows the <a href="/wiki/Syntax_(logic)" title="Syntax (logic)">syntactic</a> divisions within a <a href="/wiki/Formal_system" title="Formal system">formal system</a>. <a href="/wiki/String_(computer_science)" title="String (computer science)">Strings of symbols</a> may be broadly divided into nonsense and <a href="/wiki/Well-formed_formula" title="Well-formed formula">well-formed formulas</a>. The set of well-formed formulas is divided into <a href="/wiki/Theorem" title="Theorem">theorems</a> and non-theorems.</figcaption></figure> <p>In <a href="/wiki/Mathematical_logic" title="Mathematical logic">mathematical logic</a>, a <i>formal theory</i> is a set of <a href="/wiki/Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">sentences</a> expressed in a formal language. </p><p>A <i>formal system</i> (also called a <i>logical calculus</i>, or a <i>logical system</i>) consists of a formal language together with a <a href="/wiki/Deductive_apparatus" class="mw-redirect" title="Deductive apparatus">deductive apparatus</a> (also called a <i>deductive system</i>). The deductive apparatus may consist of a set of <a href="/wiki/Transformation_rule" class="mw-redirect" title="Transformation rule">transformation rules</a>, which may be interpreted as valid rules of inference, or a set of <a href="/wiki/Axiom" title="Axiom">axioms</a>, or have both. A formal system is used to <a href="/wiki/Proof_theory" title="Proof theory">derive</a> one expression from one or more other expressions. Although a formal language can be identified with its formulas, a formal system cannot be likewise identified by its theorems. Two formal systems <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 {FS}}}"> <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">F</mi> <mi class="MJX-tex-caligraphic" mathvariant="script">S</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {FS}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ab025245b89b5d8e91a0f027632b0c1764ab2a9f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.419ex; height:2.176ex;" alt="{\displaystyle {\mathcal {FS}}}"></span> and <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 {FS'}}}"> <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">F</mi> <msup> <mi class="MJX-tex-caligraphic" mathvariant="script">S</mi> <mo>′</mo> </msup> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {FS'}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/23a8dd711a545583eab7b71b7cf80d57ee84344c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.129ex; height:2.509ex;" alt="{\displaystyle {\mathcal {FS'}}}"></span> may have all the same theorems and yet differ in some significant proof-theoretic way (a formula A may be a syntactic consequence of a formula B in one but not another for instance). </p><p>A <i>formal proof</i> or <i>derivation</i> is a finite sequence of well-formed formulas (which may be interpreted as sentences, or <a href="/wiki/Proposition" title="Proposition">propositions</a>) each of which is an axiom or follows from the preceding formulas in the sequence by a <a href="/wiki/Rule_of_inference" title="Rule of inference">rule of inference</a>. The last sentence in the sequence is a theorem of a formal system. Formal proofs are useful because their theorems can be interpreted as true propositions. </p> <div class="mw-heading mw-heading4"><h4 id="Interpretations_and_models">Interpretations and models</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=11" title="Edit section: Interpretations and models"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main articles: <a href="/wiki/Formal_semantics_(logic)" class="mw-redirect" title="Formal semantics (logic)">Formal semantics (logic)</a>, <a href="/wiki/Interpretation_(logic)" title="Interpretation (logic)">Interpretation (logic)</a>, and <a href="/wiki/Model_theory" title="Model theory">Model theory</a></div> <p>Formal languages are entirely syntactic in nature, but may be given <a href="/wiki/Semantics" title="Semantics">semantics</a> that give meaning to the elements of the language. For instance, in mathematical <a href="/wiki/Logic" title="Logic">logic</a>, the set of possible formulas of a particular logic is a formal language, and an <a href="/wiki/Interpretation_(logic)" title="Interpretation (logic)">interpretation</a> assigns a meaning to each of the formulas—usually, a <a href="/wiki/Truth_value" title="Truth value">truth value</a>. </p><p>The study of interpretations of formal languages is called <a href="/wiki/Formal_semantics_(logic)" class="mw-redirect" title="Formal semantics (logic)">formal semantics</a>. In mathematical logic, this is often done in terms of <a href="/wiki/Model_theory" title="Model theory">model theory</a>. In model theory, the terms that occur in a formula are interpreted as objects within <a href="/wiki/Structure_(mathematical_logic)" title="Structure (mathematical logic)">mathematical structures</a>, and fixed compositional interpretation rules determine how the truth value of the formula can be derived from the interpretation of its terms; a <i>model</i> for a formula is an interpretation of terms such that the formula becomes true. </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=12" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Combinatorics_on_words" title="Combinatorics on words">Combinatorics on words</a></li> <li><a href="/wiki/Formal_method" class="mw-redirect" title="Formal method">Formal method</a></li> <li><a href="/wiki/Free_monoid" title="Free monoid">Free monoid</a></li> <li><a href="/wiki/Grammar_framework" class="mw-redirect" title="Grammar framework">Grammar framework</a></li> <li><a href="/wiki/Mathematical_notation" title="Mathematical notation">Mathematical notation</a></li> <li><a href="/wiki/String_(computer_science)" title="String (computer science)">String (computer science)</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=13" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text">For example, <a href="/wiki/First-order_logic" title="First-order logic">first-order logic</a> is often expressed using an alphabet that, besides symbols such as ∧, ¬, ∀ and parentheses, contains infinitely many elements <i>x</i><sub>0</sub>, <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, … that play the role of variables.</span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=14" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Citations">Citations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=15" title="Edit section: Citations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239543626"><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">See e.g. <style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFReghizzi2009" class="citation book cs1">Reghizzi, Stefano Crespi (2009). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=AxH6cWm61i0C"><i>Formal Languages and Compilation</i></a>. Texts in Computer Science. Springer. p. 8. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2009flc..book.....C">2009flc..book.....C</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9781848820500" title="Special:BookSources/9781848820500"><bdi>9781848820500</bdi></a>. <q>An alphabet is a finite set</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Formal+Languages+and+Compilation&rft.series=Texts+in+Computer+Science&rft.pages=8&rft.pub=Springer&rft.date=2009&rft_id=info%3Abibcode%2F2009flc..book.....C&rft.isbn=9781848820500&rft.aulast=Reghizzi&rft.aufirst=Stefano+Crespi&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DAxH6cWm61i0C&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFormal+language" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/220530857">"In the prehistory of formal language theory: Gauss Languages"</a>. January 1992<span class="reference-accessdate">. Retrieved <span class="nowrap">30 April</span> 2021</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=In+the+prehistory+of+formal+language+theory%3A+Gauss+Languages&rft.date=1992-01&rft_id=https%3A%2F%2Fwww.researchgate.net%2Fpublication%2F220530857&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFormal+language" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://plato.stanford.edu/entries/frege/">"Gottlob Frege"</a>. 5 December 2019<span class="reference-accessdate">. Retrieved <span class="nowrap">30 April</span> 2021</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Gottlob+Frege&rft.date=2019-12-05&rft_id=https%3A%2F%2Fplato.stanford.edu%2Fentries%2Ffrege%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFormal+language" class="Z3988"></span></span> </li> <li id="cite_note-Herken1279-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-Herken1279_4-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMartin_Davis1995" class="citation book cs1">Martin Davis (1995). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=YafIDVd1Z68C&pg=PA290">"Influences of Mathematical Logic on Computer Science"</a>. In Rolf Herken (ed.). <i>The universal Turing machine: a half-century survey</i>. Springer. p. 290. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-211-82637-9" title="Special:BookSources/978-3-211-82637-9"><bdi>978-3-211-82637-9</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Influences+of+Mathematical+Logic+on+Computer+Science&rft.btitle=The+universal+Turing+machine%3A+a+half-century+survey&rft.pages=290&rft.pub=Springer&rft.date=1995&rft.isbn=978-3-211-82637-9&rft.au=Martin+Davis&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DYafIDVd1Z68C%26pg%3DPA290&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFormal+language" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://core.ac.uk/download/pdf/297029993.pdf">"Thue's 1914 paper: a translation"</a> <span class="cs1-format">(PDF)</span>. 28 August 2013. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20210430011129/https://core.ac.uk/download/pdf/297029993.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 30 April 2021<span class="reference-accessdate">. Retrieved <span class="nowrap">30 April</span> 2021</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Thue%27s+1914+paper%3A+a+translation&rft.date=2013-08-28&rft_id=https%3A%2F%2Fcore.ac.uk%2Fdownload%2Fpdf%2F297029993.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFormal+language" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://mathshistory.st-andrews.ac.uk/Biographies/Post/">"Emil Leon Post"</a>. September 2001<span class="reference-accessdate">. Retrieved <span class="nowrap">30 April</span> 2021</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Emil+Leon+Post&rft.date=2001-09&rft_id=https%3A%2F%2Fmathshistory.st-andrews.ac.uk%2FBiographies%2FPost%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFormal+language" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">Torres Quevedo, Leonardo. <a rel="nofollow" class="external text" href="https://quickclick.es/rop/pdf/publico/1907/1907_tomoI_1634_01.pdf">Sobre un sistema de notaciones y símbolos destinados a facilitar la descripción de las máquinas, (pdf)</a>, pp. 25–30, Revista de Obras Públicas, 17 January 1907.</span> </li> <li id="cite_note-Bruderer-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-Bruderer_8-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBruderer2021" class="citation book cs1">Bruderer, Herbert (2021). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=Gh8SEAAAQBAJ&dq=leonardo+torres+quevedo+heinz+zemanek+formal+language&pg=PA1212">"The Global Evolution of Computer Technology"</a>. <i>Milestones in Analog and Digital Computing</i>. Springer. p. 1212. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3030409739" title="Special:BookSources/978-3030409739"><bdi>978-3030409739</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=The+Global+Evolution+of+Computer+Technology&rft.btitle=Milestones+in+Analog+and+Digital+Computing&rft.pages=1212&rft.pub=Springer&rft.date=2021&rft.isbn=978-3030409739&rft.aulast=Bruderer&rft.aufirst=Herbert&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DGh8SEAAAQBAJ%26dq%3Dleonardo%2Btorres%2Bquevedo%2Bheinz%2Bzemanek%2Bformal%2Blanguage%26pg%3DPA1212&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFormal+language" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJagerRogers2012" class="citation journal cs1">Jager, Gerhard; Rogers, James (19 July 2012). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3367686">"Formal language theory: refining the Chomsky hierarchy"</a>. <i>Philosophical Transactions of the Royal Society B</i>. <b>367</b> (1598): 1956–1970. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1098%2Frstb.2012.0077">10.1098/rstb.2012.0077</a>. <a href="/wiki/PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3367686">3367686</a></span>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/22688632">22688632</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Philosophical+Transactions+of+the+Royal+Society+B&rft.atitle=Formal+language+theory%3A+refining+the+Chomsky+hierarchy&rft.volume=367&rft.issue=1598&rft.pages=1956-1970&rft.date=2012-07-19&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC3367686%23id-name%3DPMC&rft_id=info%3Apmid%2F22688632&rft_id=info%3Adoi%2F10.1098%2Frstb.2012.0077&rft.aulast=Jager&rft.aufirst=Gerhard&rft.au=Rogers%2C+James&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC3367686&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFormal+language" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://mathshistory.st-andrews.ac.uk/Biographies/Backus/">"John Warner Backus"</a>. February 2016<span class="reference-accessdate">. Retrieved <span class="nowrap">30 April</span> 2021</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=John+Warner+Backus&rft.date=2016-02&rft_id=https%3A%2F%2Fmathshistory.st-andrews.ac.uk%2FBiographies%2FBackus%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFormal+language" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><a href="#CITEREFHopcroftUllman1979">Hopcroft & Ullman (1979)</a>, Chapter 11: Closure properties of families of languages.</span> </li> </ol></div></div> <div class="mw-heading mw-heading3"><h3 id="Sources">Sources</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=16" title="Edit section: Sources"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <dl><dt>Works cited</dt></dl> <style data-mw-deduplicate="TemplateStyles:r1239549316">.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}</style><div class="refbegin" style=""> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHopcroftUllman1979" class="citation book cs1"><a href="/wiki/John_Hopcroft" title="John Hopcroft">Hopcroft, John E.</a>; <a href="/wiki/Jeffrey_Ullman" title="Jeffrey Ullman">Ullman, Jeffrey D.</a> (1979). <i><a href="/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation" title="Introduction to Automata Theory, Languages, and Computation">Introduction to Automata Theory, Languages, and Computation</a></i>. Reading, Massachusetts: Addison-Wesley Publishing. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/81-7808-347-7" title="Special:BookSources/81-7808-347-7"><bdi>81-7808-347-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Automata+Theory%2C+Languages%2C+and+Computation&rft.place=Reading%2C+Massachusetts&rft.pub=Addison-Wesley+Publishing&rft.date=1979&rft.isbn=81-7808-347-7&rft.aulast=Hopcroft&rft.aufirst=John+E.&rft.au=Ullman%2C+Jeffrey+D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFormal+language" class="Z3988"></span></li></ul> </div> <dl><dt>General references</dt></dl> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239549316"><div class="refbegin" style=""> <ul><li>A. G. Hamilton, <i>Logic for Mathematicians</i>, <a href="/wiki/Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>, 1978, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-521-21838-1" title="Special:BookSources/0-521-21838-1">0-521-21838-1</a>.</li> <li><a href="/wiki/Seymour_Ginsburg" title="Seymour Ginsburg">Seymour Ginsburg</a>, <i>Algebraic and automata theoretic properties of formal languages</i>, North-Holland, 1975, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-7204-2506-9" title="Special:BookSources/0-7204-2506-9">0-7204-2506-9</a>.</li> <li><a href="/wiki/Michael_A._Harrison" title="Michael A. Harrison">Michael A. Harrison</a>, <i>Introduction to Formal Language Theory</i>, Addison-Wesley, 1978.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRautenberg2010" class="citation book cs1"><a href="/wiki/Wolfgang_Rautenberg" title="Wolfgang Rautenberg">Rautenberg, Wolfgang</a> (2010). <i>A Concise Introduction to Mathematical Logic</i> (3rd ed.). New York: <a href="/wiki/Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer Science+Business Media</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4419-1221-3">10.1007/978-1-4419-1221-3</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4419-1220-6" title="Special:BookSources/978-1-4419-1220-6"><bdi>978-1-4419-1220-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=A+Concise+Introduction+to+Mathematical+Logic&rft.place=New+York&rft.edition=3rd&rft.pub=Springer+Science%2BBusiness+Media&rft.date=2010&rft_id=info%3Adoi%2F10.1007%2F978-1-4419-1221-3&rft.isbn=978-1-4419-1220-6&rft.aulast=Rautenberg&rft.aufirst=Wolfgang&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFormal+language" class="Z3988"></span></li> <li><a href="/wiki/Grzegorz_Rozenberg" title="Grzegorz Rozenberg">Grzegorz Rozenberg</a>, <a href="/wiki/Arto_Salomaa" title="Arto Salomaa">Arto Salomaa</a>, <i>Handbook of Formal Languages: Volume I-III</i>, Springer, 1997, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/3-540-61486-9" title="Special:BookSources/3-540-61486-9">3-540-61486-9</a>.</li> <li>Patrick Suppes, <i>Introduction to Logic</i>, D. Van Nostrand, 1957, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-442-08072-7" title="Special:BookSources/0-442-08072-7">0-442-08072-7</a>.</li></ul> </div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Formal_language&action=edit&section=17" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation cs2"><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php?title=Formal_language">"Formal language"</a>, <i><a href="/wiki/Encyclopedia_of_Mathematics" title="Encyclopedia of Mathematics">Encyclopedia of Mathematics</a></i>, <a href="/wiki/European_Mathematical_Society" title="European Mathematical Society">EMS Press</a>, 2001 [1994]</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Formal+language&rft.btitle=Encyclopedia+of+Mathematics&rft.pub=EMS+Press&rft.date=2001&rft_id=https%3A%2F%2Fwww.encyclopediaofmath.org%2Findex.php%3Ftitle%3DFormal_language&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFormal+language" class="Z3988"></span></li> <li><a href="/wiki/University_of_Maryland,_Baltimore" title="University of Maryland, Baltimore">University of Maryland</a>, <a rel="nofollow" class="external text" href="http://www.csee.umbc.edu/help/theory/lang_def.shtml">Formal Language Definitions</a></li> <li>James Power, <a rel="nofollow" class="external text" href="http://www.cs.nuim.ie/~jpower/Courses/parsing/">"Notes on Formal Language Theory and Parsing"</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20071121142736/http://www.cs.nuim.ie/~jpower/Courses/parsing/">Archived</a> 21 November 2007 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a>, 29 November 2002.</li> <li>Drafts of some chapters in the "Handbook of Formal Language Theory", Vol. 1–3, G. Rozenberg and A. Salomaa (eds.), <a href="/wiki/Springer_Verlag" class="mw-redirect" title="Springer Verlag">Springer Verlag</a>, (1997): <ul><li>Alexandru Mateescu and Arto Salomaa, <a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~lkontor/noam/Mateescu-Salomaa.pdf">"Preface" in Vol.1, pp. v–viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp. 1–39</a></li> <li>Sheng Yu, <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.1248&rep=rep1&type=pdf">"Regular Languages", Chapter 2 in Vol. 1</a></li> <li>Jean-Michel Autebert, Jean Berstel, Luc Boasson, <a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/248295.html">"Context-Free Languages and Push-Down Automata", Chapter 3 in Vol. 1</a></li> <li>Christian Choffrut and Juhani Karhumäki, <a rel="nofollow" class="external text" href="http://www.liafa.jussieu.fr/~cc/PUBLICATIONS/CKTUCS.PS.gz">"Combinatorics of Words", Chapter 6 in Vol. 1</a></li> <li>Tero Harju and Juhani Karhumäki, <a rel="nofollow" class="external text" href="http://users.utu.fi/harju/articles/morph.pdf">"Morphisms", Chapter 7 in Vol. 1, pp. 439–510</a></li> <li>Jean-Eric Pin, <a rel="nofollow" class="external text" href="http://www.liafa.jussieu.fr/~jep/PDF/HandBook.pdf">"Syntactic semigroups", Chapter 10 in Vol. 1, pp. 679–746</a></li> <li>M. Crochemore and C. Hancart, <a rel="nofollow" class="external text" href="http://www-igm.univ-mlv.fr/~mac/REC/DOC/B4.ps">"Automata for matching patterns", Chapter 9 in Vol. 2</a></li> <li>Dora Giammarresi, Antonio Restivo, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20071008170115/http://bruno.maitresdumonde.com/optinfo/Spe-MP/dmds1998/2dlang/giammaresi-restivo-paper.ps">"Two-dimensional Languages", Chapter 4 in Vol. 3, pp. 215–267</a></li></ul></li></ul> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Automata_theory:_formal_languages_and_formal_grammars" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Formal_languages_and_grammars" title="Template:Formal languages and grammars"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Formal_languages_and_grammars" title="Template talk:Formal languages and grammars"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Formal_languages_and_grammars" title="Special:EditPage/Template:Formal languages and grammars"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Automata_theory:_formal_languages_and_formal_grammars" style="font-size:114%;margin:0 4em"><a href="/wiki/Automata_theory" title="Automata theory">Automata theory</a>: <a class="mw-selflink selflink">formal languages</a> and <a href="/wiki/Formal_grammar" title="Formal grammar">formal grammars</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd plainlist" style="width:100%;padding:0;background:transparent;color:inherit;"><div style="padding:0px"><table class="navbox-columns-table" style="border-spacing: 0px; text-align:left;width:100%;"><tbody><tr><td class="navbox-abovebelow" style="font-weight:bold;"><a href="/wiki/Chomsky_hierarchy" title="Chomsky hierarchy">Chomsky hierarchy</a></td><td class="navbox-abovebelow" style="border-left:2px solid #fdfdfd;font-weight:bold;"><a href="/wiki/Formal_grammar" title="Formal grammar">Grammars</a></td><td class="navbox-abovebelow" style="border-left:2px solid #fdfdfd;font-weight:bold;"><a class="mw-selflink selflink">Languages</a></td><td class="navbox-abovebelow" style="border-left:2px solid #fdfdfd;font-weight:bold;"><a href="/wiki/Abstract_machine" title="Abstract machine">Abstract machines</a></td></tr><tr style="vertical-align:top"><td class="navbox-list" style="padding:0px;text-align: center;width:10em;"><div> <ul><li>Type-0</li> <li>—</li> <li>Type-1</li> <li>—</li> <li>—</li> <li>—</li> <li>—</li> <li>—</li> <li>Type-2</li> <li>—</li> <li>—</li> <li>Type-3</li> <li>—</li> <li>—</li></ul> </div></td><td class="navbox-list" style="border-left:2px solid #fdfdfd;padding:0px;width:10em;"><div> <ul><li><a href="/wiki/Unrestricted_grammar" title="Unrestricted grammar">Unrestricted</a></li> <li>(no common name)</li> <li><a href="/wiki/Context-sensitive_grammar" title="Context-sensitive grammar">Context-sensitive</a></li> <li><span style="white-space:nowrap;">Positive <a href="/wiki/Range_concatenation_grammars" class="mw-redirect" title="Range concatenation grammars">range concatenation</a></span></li> <li><a href="/wiki/Indexed_grammar" title="Indexed grammar">Indexed</a></li> <li>—</li> <li><a href="/wiki/Linear_context-free_rewriting_system" class="mw-redirect" title="Linear context-free rewriting system">Linear context-free rewriting systems</a></li> <li><a href="/wiki/Tree-adjoining_grammar" title="Tree-adjoining grammar">Tree-adjoining</a></li> <li><a href="/wiki/Context-free_grammar" title="Context-free grammar">Context-free</a></li> <li><a href="/wiki/Deterministic_context-free_grammar" title="Deterministic context-free grammar">Deterministic context-free</a></li> <li><a href="/wiki/Nested_word" title="Nested word">Visibly pushdown</a></li> <li><a href="/wiki/Regular_grammar" title="Regular grammar">Regular</a></li> <li>—</li> <li><a href="/wiki/Non-recursive_grammar" class="mw-redirect" title="Non-recursive grammar">Non-recursive</a></li></ul> </div></td><td class="navbox-list" style="border-left:2px solid #fdfdfd;padding:0px;width:10em;"><div> <ul><li><a href="/wiki/Recursively_enumerable_language" title="Recursively enumerable language">Recursively enumerable</a></li> <li><a href="/wiki/Recursive_language" title="Recursive language">Decidable</a></li> <li><a href="/wiki/Context-sensitive_language" title="Context-sensitive language">Context-sensitive</a></li> <li><span style="white-space:nowrap;">Positive <a href="/wiki/Range_concatenation_language" class="mw-redirect" title="Range concatenation language">range concatenation</a><sup>*</sup></span></li> <li><a href="/wiki/Indexed_language" title="Indexed language">Indexed</a><sup>*</sup></li> <li>—</li> <li><a href="/wiki/Linear_context-free_rewriting_language" class="mw-redirect" title="Linear context-free rewriting language">Linear context-free rewriting language</a></li> <li><a href="/wiki/Tree-adjoining_grammar" title="Tree-adjoining grammar">Tree-adjoining</a></li> <li><a href="/wiki/Context-free_language" title="Context-free language">Context-free</a></li> <li><a href="/wiki/Deterministic_context-free_language" title="Deterministic context-free language">Deterministic context-free</a></li> <li><a href="/wiki/Nested_word" title="Nested word">Visibly pushdown</a></li> <li><a href="/wiki/Regular_language" title="Regular language">Regular</a></li> <li><a href="/wiki/Star-free_language" title="Star-free language">Star-free</a></li> <li><a href="/wiki/Finite_language" class="mw-redirect" title="Finite language">Finite</a></li></ul> </div></td><td class="navbox-list" style="border-left:2px solid #fdfdfd;padding:0px;width:10em;"><div> <ul><li><a href="/wiki/Turing_machine" title="Turing machine">Turing machine</a></li> <li><a href="/wiki/Decider_(Turing_machine)" title="Decider (Turing machine)">Decider</a></li> <li><a href="/wiki/Linear_bounded_automaton" title="Linear bounded automaton">Linear-bounded</a></li> <li><a href="/wiki/PTIME" class="mw-redirect" title="PTIME">PTIME</a> Turing Machine</li> <li><a href="/wiki/Nested_stack_automaton" title="Nested stack automaton">Nested stack</a></li> <li><a href="/wiki/Thread_automaton" title="Thread automaton">Thread automaton</a></li> <li>restricted <a href="/wiki/Tree_stack_automaton" title="Tree stack automaton">Tree stack automaton</a></li> <li><a href="/wiki/Embedded_pushdown_automaton" title="Embedded pushdown automaton">Embedded pushdown</a></li> <li><a href="/wiki/Pushdown_automaton" title="Pushdown automaton">Nondeterministic pushdown</a></li> <li><a href="/wiki/Deterministic_pushdown_automaton" title="Deterministic pushdown automaton">Deterministic pushdown</a></li> <li><a href="/wiki/Nested_word" title="Nested word">Visibly pushdown</a></li> <li><a href="/wiki/Finite-state_machine" title="Finite-state machine">Finite</a></li> <li><a href="/wiki/Aperiodic_finite_state_automaton" title="Aperiodic finite state automaton">Counter-free (with aperiodic finite monoid)</a></li> <li><a href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Acyclic finite</a></li></ul> </div></td></tr></tbody></table></div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><span style="white-space:nowrap;">Each category of languages, except those marked by a <sup>*</sup>, is a <a href="/wiki/Proper_subset" class="mw-redirect" title="Proper subset">proper subset</a> of the category directly above it.</span> <span style="white-space:nowrap;">Any language in each category is generated by a grammar and by an automaton in the category in the same line.</span></div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox" aria-labelledby="Mathematical_logic" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Mathematical_logic" title="Template:Mathematical logic"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Mathematical_logic" title="Template talk:Mathematical logic"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Mathematical_logic" title="Special:EditPage/Template:Mathematical logic"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Mathematical_logic" style="font-size:114%;margin:0 4em"><a href="/wiki/Mathematical_logic" title="Mathematical logic">Mathematical logic</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Axiom" title="Axiom">Axiom</a> <ul><li><a href="/wiki/List_of_axioms" title="List of axioms">list</a></li></ul></li> <li><a href="/wiki/Cardinality" title="Cardinality">Cardinality</a></li> <li><a href="/wiki/First-order_logic" title="First-order logic">First-order logic</a></li> <li><a href="/wiki/Formal_proof" title="Formal proof">Formal proof</a></li> <li><a href="/wiki/Formal_semantics_(logic)" class="mw-redirect" title="Formal semantics (logic)">Formal semantics</a></li> <li><a href="/wiki/Foundations_of_mathematics" title="Foundations of mathematics">Foundations of mathematics</a></li> <li><a href="/wiki/Information_theory" title="Information theory">Information theory</a></li> <li><a href="/wiki/Lemma_(mathematics)" title="Lemma (mathematics)">Lemma</a></li> <li><a href="/wiki/Logical_consequence" title="Logical consequence">Logical consequence</a></li> <li><a href="/wiki/Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a></li> <li><a href="/wiki/Theorem" title="Theorem">Theorem</a></li> <li><a href="/wiki/Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a></li> <li><a href="/wiki/Type_theory" title="Type theory">Type theory</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems (<a href="/wiki/Category:Theorems_in_the_foundations_of_mathematics" title="Category:Theorems in the foundations of mathematics">list</a>)<br /> and <a href="/wiki/Paradoxes_of_set_theory" title="Paradoxes of set theory">paradoxes</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/G%C3%B6del%27s_completeness_theorem" title="Gödel's completeness theorem">Gödel's completeness</a> and <a href="/wiki/G%C3%B6del%27s_incompleteness_theorems" title="Gödel's incompleteness theorems">incompleteness theorems</a></li> <li><a href="/wiki/Tarski%27s_undefinability_theorem" title="Tarski's undefinability theorem">Tarski's undefinability</a></li> <li><a href="/wiki/Banach%E2%80%93Tarski_paradox" title="Banach–Tarski paradox">Banach–Tarski paradox</a></li> <li>Cantor's <a href="/wiki/Cantor%27s_theorem" title="Cantor's theorem">theorem,</a> <a href="/wiki/Cantor%27s_paradox" title="Cantor's paradox">paradox</a> and <a href="/wiki/Cantor%27s_diagonal_argument" title="Cantor's diagonal argument">diagonal argument</a></li> <li><a href="/wiki/Compactness_theorem" title="Compactness theorem">Compactness</a></li> <li><a href="/wiki/Halting_problem" title="Halting problem">Halting problem</a></li> <li><a href="/wiki/Lindstr%C3%B6m%27s_theorem" title="Lindström's theorem">Lindström's</a></li> <li><a href="/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem" title="Löwenheim–Skolem theorem">Löwenheim–Skolem</a></li> <li><a href="/wiki/Russell%27s_paradox" title="Russell's paradox">Russell's paradox</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Logic" title="Logic">Logics</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Traditional" scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Term_logic" title="Term logic">Traditional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Classical_logic" title="Classical logic">Classical logic</a></li> <li><a href="/wiki/Logical_truth" title="Logical truth">Logical truth</a></li> <li><a href="/wiki/Tautology_(logic)" title="Tautology (logic)">Tautology</a></li> <li><a href="/wiki/Proposition" title="Proposition">Proposition</a></li> <li><a href="/wiki/Inference" title="Inference">Inference</a></li> <li><a href="/wiki/Logical_equivalence" title="Logical equivalence">Logical equivalence</a></li> <li><a href="/wiki/Consistency" title="Consistency">Consistency</a> <ul><li><a href="/wiki/Equiconsistency" title="Equiconsistency">Equiconsistency</a></li></ul></li> <li><a href="/wiki/Argument" title="Argument">Argument</a></li> <li><a href="/wiki/Soundness" title="Soundness">Soundness</a></li> <li><a href="/wiki/Validity_(logic)" title="Validity (logic)">Validity</a></li> <li><a href="/wiki/Syllogism" title="Syllogism">Syllogism</a></li> <li><a href="/wiki/Square_of_opposition" title="Square of opposition">Square of opposition</a></li> <li><a href="/wiki/Venn_diagram" title="Venn diagram">Venn diagram</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Propositional_calculus" title="Propositional calculus">Propositional</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Boolean_algebra" title="Boolean algebra">Boolean algebra</a></li> <li><a href="/wiki/Boolean_function" title="Boolean function">Boolean functions</a></li> <li><a href="/wiki/Logical_connective" title="Logical connective">Logical connectives</a></li> <li><a href="/wiki/Propositional_calculus" title="Propositional calculus">Propositional calculus</a></li> <li><a href="/wiki/Propositional_formula" title="Propositional formula">Propositional formula</a></li> <li><a href="/wiki/Truth_table" title="Truth table">Truth tables</a></li> <li><a href="/wiki/Many-valued_logic" title="Many-valued logic">Many-valued logic</a> <ul><li><a href="/wiki/Three-valued_logic" title="Three-valued logic">3</a></li> <li><a href="/wiki/Finite-valued_logic" title="Finite-valued logic">finite</a></li> <li><a href="/wiki/Infinite-valued_logic" title="Infinite-valued logic">∞</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Predicate_logic" class="mw-redirect" title="Predicate logic">Predicate</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/First-order_logic" title="First-order logic">First-order</a> <ul><li><a href="/wiki/List_of_first-order_theories" title="List of first-order theories"><span style="font-size:85%;">list</span></a></li></ul></li> <li><a href="/wiki/Second-order_logic" title="Second-order logic">Second-order</a> <ul><li><a href="/wiki/Monadic_second-order_logic" title="Monadic second-order logic">Monadic</a></li></ul></li> <li><a href="/wiki/Higher-order_logic" title="Higher-order logic">Higher-order</a></li> <li><a href="/wiki/Fixed-point_logic" title="Fixed-point logic">Fixed-point</a></li> <li><a href="/wiki/Free_logic" title="Free logic">Free</a></li> <li><a href="/wiki/Quantifier_(logic)" title="Quantifier (logic)">Quantifiers</a></li> <li><a href="/wiki/Predicate_(mathematical_logic)" title="Predicate (mathematical logic)">Predicate</a></li> <li><a href="/wiki/Monadic_predicate_calculus" title="Monadic predicate calculus">Monadic predicate calculus</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Set_theory" title="Set theory">Set theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Zermelo%E2%80%93Fraenkel_set_theory" title="Zermelo–Fraenkel set theory">Set</a> <ul><li><a href="/wiki/Hereditary_set" title="Hereditary set">hereditary</a></li></ul></li> <li><a href="/wiki/Class_(set_theory)" title="Class (set theory)">Class</a></li> <li>(<a href="/wiki/Urelement" title="Urelement">Ur-</a>)<a href="/wiki/Element_(mathematics)" title="Element (mathematics)">Element</a></li> <li><a href="/wiki/Ordinal_number" title="Ordinal number">Ordinal number</a></li> <li><a href="/wiki/Extensionality" title="Extensionality">Extensionality</a></li> <li><a href="/wiki/Forcing_(mathematics)" title="Forcing (mathematics)">Forcing</a></li> <li><a href="/wiki/Relation_(mathematics)" title="Relation (mathematics)">Relation</a> <ul><li><a href="/wiki/Equivalence_relation" title="Equivalence relation">equivalence</a></li> <li><a href="/wiki/Partition_of_a_set" title="Partition of a set">partition</a></li></ul></li> <li>Set operations: <ul><li><a href="/wiki/Intersection_(set_theory)" title="Intersection (set theory)">intersection</a></li> <li><a href="/wiki/Union_(set_theory)" title="Union (set theory)">union</a></li> <li><a href="/wiki/Complement_(set_theory)" title="Complement (set theory)">complement</a></li> <li><a href="/wiki/Cartesian_product" title="Cartesian product">Cartesian product</a></li> <li><a href="/wiki/Power_set" title="Power set">power set</a></li> <li><a href="/wiki/List_of_set_identities_and_relations" title="List of set identities and relations">identities</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types of <a href="/wiki/Set_(mathematics)" title="Set (mathematics)">sets</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Countable_set" title="Countable set">Countable</a></li> <li><a href="/wiki/Uncountable_set" title="Uncountable set">Uncountable</a></li> <li><a href="/wiki/Empty_set" title="Empty set">Empty</a></li> <li><a href="/wiki/Inhabited_set" title="Inhabited set">Inhabited</a></li> <li><a href="/wiki/Singleton_(mathematics)" title="Singleton (mathematics)">Singleton</a></li> <li><a href="/wiki/Finite_set" title="Finite set">Finite</a></li> <li><a href="/wiki/Infinite_set" title="Infinite set">Infinite</a></li> <li><a href="/wiki/Transitive_set" title="Transitive set">Transitive</a></li> <li><a href="/wiki/Ultrafilter_(set_theory)" class="mw-redirect" title="Ultrafilter (set theory)">Ultrafilter</a></li> <li><a href="/wiki/Recursive_set" class="mw-redirect" title="Recursive set">Recursive</a></li> <li><a href="/wiki/Fuzzy_set" title="Fuzzy set">Fuzzy</a></li> <li><a href="/wiki/Universal_set" title="Universal set">Universal</a></li> <li><a href="/wiki/Universe_(mathematics)" title="Universe (mathematics)">Universe</a> <ul><li><a href="/wiki/Constructible_universe" title="Constructible universe">constructible</a></li> <li><a href="/wiki/Grothendieck_universe" title="Grothendieck universe">Grothendieck</a></li> <li><a href="/wiki/Von_Neumann_universe" title="Von Neumann universe">Von Neumann</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Map_(mathematics)" title="Map (mathematics)">Maps</a> and <a href="/wiki/Cardinality" title="Cardinality">cardinality</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Function_(mathematics)" title="Function (mathematics)">Function</a>/<a href="/wiki/Map_(mathematics)" title="Map (mathematics)">Map</a> <ul><li><a href="/wiki/Domain_of_a_function" title="Domain of a function">domain</a></li> <li><a href="/wiki/Codomain" title="Codomain">codomain</a></li> <li><a href="/wiki/Image_(mathematics)" title="Image (mathematics)">image</a></li></ul></li> <li><a href="/wiki/Injective_function" title="Injective function">In</a>/<a href="/wiki/Surjective_function" title="Surjective function">Sur</a>/<a href="/wiki/Bijection" title="Bijection">Bi</a>-jection</li> <li><a href="/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem" title="Schröder–Bernstein theorem">Schröder–Bernstein theorem</a></li> <li><a href="/wiki/Isomorphism" title="Isomorphism">Isomorphism</a></li> <li><a href="/wiki/G%C3%B6del_numbering" title="Gödel numbering">Gödel numbering</a></li> <li><a href="/wiki/Enumeration" title="Enumeration">Enumeration</a></li> <li><a href="/wiki/Large_cardinal" title="Large cardinal">Large cardinal</a> <ul><li><a href="/wiki/Inaccessible_cardinal" title="Inaccessible cardinal">inaccessible</a></li></ul></li> <li><a href="/wiki/Aleph_number" title="Aleph number">Aleph number</a></li> <li><a href="/wiki/Operation_(mathematics)" title="Operation (mathematics)">Operation</a> <ul><li><a href="/wiki/Binary_operation" title="Binary operation">binary</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Set theories</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Zermelo%E2%80%93Fraenkel_set_theory" title="Zermelo–Fraenkel set theory">Zermelo–Fraenkel</a> <ul><li><a href="/wiki/Axiom_of_choice" title="Axiom of choice">axiom of choice</a></li> <li><a href="/wiki/Continuum_hypothesis" title="Continuum hypothesis">continuum hypothesis</a></li></ul></li> <li><a href="/wiki/General_set_theory" title="General set theory">General</a></li> <li><a href="/wiki/Kripke%E2%80%93Platek_set_theory" title="Kripke–Platek set theory">Kripke–Platek</a></li> <li><a href="/wiki/Morse%E2%80%93Kelley_set_theory" title="Morse–Kelley set theory">Morse–Kelley</a></li> <li><a href="/wiki/Naive_set_theory" title="Naive set theory">Naive</a></li> <li><a href="/wiki/New_Foundations" title="New Foundations">New Foundations</a></li> <li><a href="/wiki/Tarski%E2%80%93Grothendieck_set_theory" title="Tarski–Grothendieck set theory">Tarski–Grothendieck</a></li> <li><a href="/wiki/Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory" title="Von Neumann–Bernays–Gödel set theory">Von Neumann–Bernays–Gödel</a></li> <li><a href="/wiki/Ackermann_set_theory" title="Ackermann set theory">Ackermann</a></li> <li><a href="/wiki/Constructive_set_theory" title="Constructive set theory">Constructive</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Formal_system" title="Formal system">Formal systems</a> (<a href="/wiki/List_of_formal_systems" title="List of formal systems"><span style="font-size:85%;">list</span></a>),<br /><a class="mw-selflink selflink">language</a> and <a href="/wiki/Syntax_(logic)" title="Syntax (logic)">syntax</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Alphabet_(formal_languages)" title="Alphabet (formal languages)">Alphabet</a></li> <li><a href="/wiki/Arity" title="Arity">Arity</a></li> <li><a href="/wiki/Automata_theory" title="Automata theory">Automata</a></li> <li><a href="/wiki/Axiom_schema" title="Axiom schema">Axiom schema</a></li> <li><a href="/wiki/Expression_(mathematics)" title="Expression (mathematics)">Expression</a> <ul><li><a href="/wiki/Ground_expression" title="Ground expression">ground</a></li></ul></li> <li><a href="/wiki/Extension_by_new_constant_and_function_names" title="Extension by new constant and function names">Extension</a> <ul><li><a href="/wiki/Extension_by_definitions" title="Extension by definitions">by definition</a></li> <li><a href="/wiki/Conservative_extension" title="Conservative extension">conservative</a></li></ul></li> <li><a href="/wiki/Finitary_relation" title="Finitary relation">Relation</a></li> <li><a href="/wiki/Formation_rule" title="Formation rule">Formation rule</a></li> <li><a href="/wiki/Formal_grammar" title="Formal grammar">Grammar</a></li> <li><a href="/wiki/Well-formed_formula" title="Well-formed formula">Formula</a> <ul><li><a href="/wiki/Atomic_formula" title="Atomic formula">atomic</a></li> <li><a href="/wiki/Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">closed</a></li> <li><a href="/wiki/Ground_formula" class="mw-redirect" title="Ground formula">ground</a></li> <li><a href="/wiki/Open_formula" title="Open formula">open</a></li></ul></li> <li><a href="/wiki/Free_variables_and_bound_variables" title="Free variables and bound variables">Free/bound variable</a></li> <li><a class="mw-selflink selflink">Language</a></li> <li><a href="/wiki/Metalanguage" title="Metalanguage">Metalanguage</a></li> <li><a href="/wiki/Logical_connective" title="Logical connective">Logical connective</a> <ul><li><a href="/wiki/Negation" title="Negation">¬</a></li> <li><a href="/wiki/Logical_disjunction" title="Logical disjunction">∨</a></li> <li><a href="/wiki/Logical_conjunction" title="Logical conjunction">∧</a></li> <li><a href="/wiki/Material_conditional" title="Material conditional">→</a></li> <li><a href="/wiki/Logical_biconditional" title="Logical biconditional">↔</a></li> <li><a href="/wiki/Logical_equality" title="Logical equality">=</a></li></ul></li> <li><a href="/wiki/Predicate_(mathematical_logic)" title="Predicate (mathematical logic)">Predicate</a> <ul><li><a href="/wiki/Functional_predicate" title="Functional predicate">functional</a></li> <li><a href="/wiki/Predicate_variable" title="Predicate variable">variable</a></li> <li><a href="/wiki/Propositional_variable" title="Propositional variable">propositional variable</a></li></ul></li> <li><a href="/wiki/Formal_proof" title="Formal proof">Proof</a></li> <li><a href="/wiki/Quantifier_(logic)" title="Quantifier (logic)">Quantifier</a> <ul><li><a href="/wiki/Existential_quantification" title="Existential quantification">∃</a></li> <li><a href="/wiki/Uniqueness_quantification" title="Uniqueness quantification">!</a></li> <li><a href="/wiki/Universal_quantification" title="Universal quantification">∀</a></li> <li><a href="/wiki/Quantifier_rank" title="Quantifier rank">rank</a></li></ul></li> <li><a href="/wiki/Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">Sentence</a> <ul><li><a href="/wiki/Atomic_sentence" title="Atomic sentence">atomic</a></li> <li><a href="/wiki/Spectrum_of_a_sentence" title="Spectrum of a sentence">spectrum</a></li></ul></li> <li><a href="/wiki/Signature_(logic)" title="Signature (logic)">Signature</a></li> <li><a href="/wiki/String_(formal_languages)" class="mw-redirect" title="String (formal languages)">String</a></li> <li><a href="/wiki/Substitution_(logic)" title="Substitution (logic)">Substitution</a></li> <li><a href="/wiki/Symbol_(formal)" title="Symbol (formal)">Symbol</a> <ul><li><a href="/wiki/Uninterpreted_function" title="Uninterpreted function">function</a></li> <li><a href="/wiki/Logical_constant" title="Logical constant">logical/constant</a></li> <li><a href="/wiki/Non-logical_symbol" title="Non-logical symbol">non-logical</a></li> <li><a href="/wiki/Variable_(mathematics)" title="Variable (mathematics)">variable</a></li></ul></li> <li><a href="/wiki/Term_(logic)" title="Term (logic)">Term</a></li> <li><a href="/wiki/Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a> <ul><li><a href="/wiki/List_of_mathematical_theories" title="List of mathematical theories"><span style="font-size:85%;">list</span></a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><span class="nowrap">Example <a href="/wiki/Axiomatic_system" title="Axiomatic system">axiomatic<br />systems</a> <span style="font-size:85%;">(<a href="/wiki/List_of_first-order_theories" title="List of first-order theories">list</a>)</span></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li>of <a href="/wiki/True_arithmetic" title="True arithmetic">arithmetic</a>: <ul><li><a href="/wiki/Peano_axioms" title="Peano axioms">Peano</a></li> <li><a href="/wiki/Second-order_arithmetic" title="Second-order arithmetic">second-order</a></li> <li><a href="/wiki/Elementary_function_arithmetic" title="Elementary function arithmetic">elementary function</a></li> <li><a href="/wiki/Primitive_recursive_arithmetic" title="Primitive recursive arithmetic">primitive recursive</a></li> <li><a href="/wiki/Robinson_arithmetic" title="Robinson arithmetic">Robinson</a></li> <li><a href="/wiki/Skolem_arithmetic" title="Skolem arithmetic">Skolem</a></li></ul></li> <li>of the <a href="/wiki/Construction_of_the_real_numbers" title="Construction of the real numbers">real numbers</a> <ul><li><a href="/wiki/Tarski%27s_axiomatization_of_the_reals" title="Tarski's axiomatization of the reals">Tarski's axiomatization</a></li></ul></li> <li>of <a href="/wiki/Axiomatization_of_Boolean_algebras" class="mw-redirect" title="Axiomatization of Boolean algebras">Boolean algebras</a> <ul><li><a href="/wiki/Boolean_algebras_canonically_defined" title="Boolean algebras canonically defined">canonical</a></li> <li><a href="/wiki/Minimal_axioms_for_Boolean_algebra" title="Minimal axioms for Boolean algebra">minimal axioms</a></li></ul></li> <li>of <a href="/wiki/Foundations_of_geometry" title="Foundations of geometry">geometry</a>: <ul><li><a href="/wiki/Euclidean_geometry" title="Euclidean geometry">Euclidean</a>: <ul><li><a href="/wiki/Euclid%27s_Elements" title="Euclid's Elements"><i>Elements</i></a></li> <li><a href="/wiki/Hilbert%27s_axioms" title="Hilbert's axioms">Hilbert's</a></li> <li><a href="/wiki/Tarski%27s_axioms" title="Tarski's axioms">Tarski's</a></li></ul></li> <li><a href="/wiki/Non-Euclidean_geometry" title="Non-Euclidean geometry">non-Euclidean</a></li></ul></li></ul> <ul><li><i><a href="/wiki/Principia_Mathematica" title="Principia Mathematica">Principia Mathematica</a></i></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Proof_theory" title="Proof theory">Proof theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Formal_proof" title="Formal proof">Formal proof</a></li> <li><a href="/wiki/Natural_deduction" title="Natural deduction">Natural deduction</a></li> <li><a href="/wiki/Logical_consequence" title="Logical consequence">Logical consequence</a></li> <li><a href="/wiki/Rule_of_inference" title="Rule of inference">Rule of inference</a></li> <li><a href="/wiki/Sequent_calculus" title="Sequent calculus">Sequent calculus</a></li> <li><a href="/wiki/Theorem" title="Theorem">Theorem</a></li> <li><a href="/wiki/Formal_system" title="Formal system">Systems</a> <ul><li><a href="/wiki/Axiomatic_system" title="Axiomatic system">axiomatic</a></li> <li><a href="/wiki/Deductive_system" class="mw-redirect" title="Deductive system">deductive</a></li> <li><a href="/wiki/Hilbert_system" title="Hilbert system">Hilbert</a> <ul><li><a href="/wiki/List_of_Hilbert_systems" class="mw-redirect" title="List of Hilbert systems">list</a></li></ul></li></ul></li> <li><a href="/wiki/Complete_theory" title="Complete theory">Complete theory</a></li> <li><a href="/wiki/Independence_(mathematical_logic)" title="Independence (mathematical logic)">Independence</a> (<a href="/wiki/List_of_statements_independent_of_ZFC" title="List of statements independent of ZFC">from ZFC</a>)</li> <li><a href="/wiki/Proof_of_impossibility" title="Proof of impossibility">Proof of impossibility</a></li> <li><a href="/wiki/Ordinal_analysis" title="Ordinal analysis">Ordinal analysis</a></li> <li><a href="/wiki/Reverse_mathematics" title="Reverse mathematics">Reverse mathematics</a></li> <li><a href="/wiki/Self-verifying_theories" title="Self-verifying theories">Self-verifying theories</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Model_theory" title="Model theory">Model theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Interpretation_(logic)" title="Interpretation (logic)">Interpretation</a> <ul><li><a href="/wiki/Interpretation_function" class="mw-redirect" title="Interpretation function">function</a></li> <li><a href="/wiki/Interpretation_(model_theory)" title="Interpretation (model theory)">of models</a></li></ul></li> <li><a href="/wiki/Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a> <ul><li><a href="/wiki/Elementary_equivalence" title="Elementary equivalence">equivalence</a></li> <li><a href="/wiki/Finite_model_theory" title="Finite model theory">finite</a></li> <li><a href="/wiki/Saturated_model" title="Saturated model">saturated</a></li> <li><a href="/wiki/Spectrum_of_a_theory" title="Spectrum of a theory">spectrum</a></li> <li><a href="/wiki/Substructure_(mathematics)" title="Substructure (mathematics)">submodel</a></li></ul></li> <li><a href="/wiki/Non-standard_model" title="Non-standard model">Non-standard model</a> <ul><li><a href="/wiki/Non-standard_model_of_arithmetic" title="Non-standard model of arithmetic">of arithmetic</a></li></ul></li> <li><a href="/wiki/Diagram_(mathematical_logic)" title="Diagram (mathematical logic)">Diagram</a> <ul><li><a href="/wiki/Elementary_diagram" title="Elementary diagram">elementary</a></li></ul></li> <li><a href="/wiki/Categorical_theory" title="Categorical theory">Categorical theory</a></li> <li><a href="/wiki/Model_complete_theory" title="Model complete theory">Model complete theory</a></li> <li><a href="/wiki/Satisfiability" title="Satisfiability">Satisfiability</a></li> <li><a href="/wiki/Semantics_of_logic" title="Semantics of logic">Semantics of logic</a></li> <li><a href="/wiki/Strength_(mathematical_logic)" title="Strength (mathematical logic)">Strength</a></li> <li><a href="/wiki/Theories_of_truth" class="mw-redirect" title="Theories of truth">Theories of truth</a> <ul><li><a href="/wiki/Semantic_theory_of_truth" title="Semantic theory of truth">semantic</a></li> <li><a href="/wiki/Tarski%27s_theory_of_truth" class="mw-redirect" title="Tarski's theory of truth">Tarski's</a></li> <li><a href="/wiki/Kripke%27s_theory_of_truth" class="mw-redirect" title="Kripke's theory of truth">Kripke's</a></li></ul></li> <li><a href="/wiki/T-schema" title="T-schema">T-schema</a></li> <li><a href="/wiki/Transfer_principle" title="Transfer principle">Transfer principle</a></li> <li><a href="/wiki/Truth_predicate" title="Truth predicate">Truth predicate</a></li> <li><a href="/wiki/Truth_value" title="Truth value">Truth value</a></li> <li><a href="/wiki/Type_(model_theory)" title="Type (model theory)">Type</a></li> <li><a href="/wiki/Ultraproduct" title="Ultraproduct">Ultraproduct</a></li> <li><a href="/wiki/Validity_(logic)" title="Validity (logic)">Validity</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Computability_theory" title="Computability theory">Computability theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Church_encoding" title="Church encoding">Church encoding</a></li> <li><a href="/wiki/Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a></li> <li><a href="/wiki/Computably_enumerable_set" title="Computably enumerable set">Computably enumerable</a></li> <li><a href="/wiki/Computable_function" title="Computable function">Computable function</a></li> <li><a href="/wiki/Computable_set" title="Computable set">Computable set</a></li> <li><a href="/wiki/Decision_problem" title="Decision problem">Decision problem</a> <ul><li><a href="/wiki/Decidability_(logic)" title="Decidability (logic)">decidable</a></li> <li><a href="/wiki/Undecidable_problem" title="Undecidable problem">undecidable</a></li> <li><a href="/wiki/P_(complexity)" title="P (complexity)">P</a></li> <li><a href="/wiki/NP_(complexity)" title="NP (complexity)">NP</a></li> <li><a href="/wiki/P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a></li></ul></li> <li><a href="/wiki/Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li> <li><a href="/wiki/Lambda_calculus" title="Lambda calculus">Lambda calculus</a></li> <li><a href="/wiki/Primitive_recursive_function" title="Primitive recursive function">Primitive recursive function</a></li> <li><a href="/wiki/Recursion" title="Recursion">Recursion</a></li> <li><a href="/wiki/Recursive_set" class="mw-redirect" title="Recursive set">Recursive set</a></li> <li><a href="/wiki/Turing_machine" title="Turing machine">Turing machine</a></li> <li><a href="/wiki/Type_theory" title="Type theory">Type theory</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Abstract_logic" title="Abstract logic">Abstract logic</a></li> <li><a href="/wiki/Algebraic_logic" title="Algebraic logic">Algebraic logic</a></li> <li><a href="/wiki/Automated_theorem_proving" title="Automated theorem proving">Automated theorem proving</a></li> <li><a href="/wiki/Category_theory" title="Category theory">Category theory</a></li> <li><a href="/wiki/Concrete_category" title="Concrete category">Concrete</a>/<a href="/wiki/Category_(mathematics)" title="Category (mathematics)">Abstract category</a></li> <li><a href="/wiki/Category_of_sets" title="Category of sets">Category of sets</a></li> <li><a href="/wiki/History_of_logic" title="History of logic">History of logic</a></li> <li><a href="/wiki/History_of_mathematical_logic" class="mw-redirect" title="History of mathematical logic">History of mathematical logic</a> <ul><li><a href="/wiki/Timeline_of_mathematical_logic" title="Timeline of mathematical logic">timeline</a></li></ul></li> <li><a href="/wiki/Logicism" title="Logicism">Logicism</a></li> <li><a href="/wiki/Mathematical_object" title="Mathematical object">Mathematical object</a></li> <li><a href="/wiki/Philosophy_of_mathematics" title="Philosophy of mathematics">Philosophy of mathematics</a></li> <li><a href="/wiki/Supertask" title="Supertask">Supertask</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><b><span class="nowrap"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Nuvola_apps_edu_mathematics_blue-p.svg" class="mw-file-description"><img alt="icon" src="//upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/16px-Nuvola_apps_edu_mathematics_blue-p.svg.png" decoding="async" width="16" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/24px-Nuvola_apps_edu_mathematics_blue-p.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/32px-Nuvola_apps_edu_mathematics_blue-p.svg.png 2x" data-file-width="128" data-file-height="128" /></a></span> </span><a href="/wiki/Portal:Mathematics" title="Portal:Mathematics">Mathematics portal</a></b></div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"><style data-mw-deduplicate="TemplateStyles:r1038841319">.mw-parser-output .tooltip-dotted{border-bottom:1px dotted;cursor:help}</style><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1038841319"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1038841319"></div><div role="navigation" class="navbox authority-control" aria-label="Navbox" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Help:Authority_control" title="Help:Authority control">Authority control databases</a>: National <span class="mw-valign-text-top noprint" typeof="mw:File/Frameless"><a href="https://www.wikidata.org/wiki/Q192161#identifiers" title="Edit this at Wikidata"><img alt="Edit this at Wikidata" src="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/10px-OOjs_UI_icon_edit-ltr-progressive.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/15px-OOjs_UI_icon_edit-ltr-progressive.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/20px-OOjs_UI_icon_edit-ltr-progressive.svg.png 2x" data-file-width="20" data-file-height="20" /></a></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4017848-1">Germany</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/sh85050802">United States</a></span></li><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="Langages formels"><a rel="nofollow" class="external text" href="https://catalogue.bnf.fr/ark:/12148/cb11967270h">France</a></span></span></li><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="Langages formels"><a rel="nofollow" class="external text" href="https://data.bnf.fr/ark:/12148/cb11967270h">BnF data</a></span></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://id.ndl.go.jp/auth/ndlna/00576869">Japan</a></span></li><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="formální jazyky"><a rel="nofollow" class="external text" href="https://aleph.nkp.cz/F/?func=find-c&local_base=aut&ccl_term=ica=ph208851&CON_LNG=ENG">Czech Republic</a></span></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="http://olduli.nli.org.il/F/?func=find-b&local_base=NLX10&find_code=UID&request=987007545721205171">Israel</a></span></li></ul></div></td></tr></tbody></table></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="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Formal_language&oldid=1244534630">https://en.wikipedia.org/w/index.php?title=Formal_language&oldid=1244534630</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Formal_languages" title="Category:Formal languages">Formal languages</a></li><li><a href="/wiki/Category:Theoretical_computer_science" title="Category:Theoretical computer science">Theoretical computer science</a></li><li><a href="/wiki/Category:Combinatorics_on_words" title="Category:Combinatorics on words">Combinatorics on words</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_March_2024" title="Category:Articles needing additional references from March 2024">Articles needing additional references from March 2024</a></li><li><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></li><li><a href="/wiki/Category:Use_dmy_dates_from_November_2023" title="Category:Use dmy dates from November 2023">Use dmy dates from November 2023</a></li><li><a href="/wiki/Category:Articles_to_be_expanded_from_March_2021" title="Category:Articles to be expanded from March 2021">Articles to be expanded from March 2021</a></li><li><a href="/wiki/Category:All_articles_to_be_expanded" title="Category:All articles to be expanded">All articles to be expanded</a></li><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</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"> This page was last edited on 7 September 2024, at 17:51<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Formal_language&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</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-f69cdc8f6-c8xbz","wgBackendResponseTime":195,"wgPageParseReport":{"limitreport":{"cputime":"0.866","walltime":"1.160","ppvisitednodes":{"value":3645,"limit":1000000},"postexpandincludesize":{"value":135861,"limit":2097152},"templateargumentsize":{"value":2727,"limit":2097152},"expansiondepth":{"value":14,"limit":100},"expensivefunctioncount":{"value":14,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":89553,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 868.616 1 -total"," 23.82% 206.876 2 Template:Reflist"," 15.23% 132.330 1 Template:Formal_languages"," 14.70% 127.707 1 Template:Sidebar_with_collapsible_lists"," 13.83% 120.142 5 Template:Cite_book"," 10.59% 92.023 1 Template:More_citations_needed"," 10.53% 91.495 2 Template:Ambox"," 9.11% 79.172 1 Template:Short_description"," 6.51% 56.531 1 Template:Formal_languages_and_grammars"," 5.99% 51.997 1 Template:Navbox_with_columns"]},"scribunto":{"limitreport-timeusage":{"value":"0.487","limit":"10.000"},"limitreport-memusage":{"value":7892187,"limit":52428800},"limitreport-logs":"anchor_id_list = table#1 {\n [\"CITEREFBruderer2021\"] = 1,\n [\"CITEREFHopcroftUllman1979\"] = 1,\n [\"CITEREFJagerRogers2012\"] = 1,\n [\"CITEREFMartin_Davis1995\"] = 1,\n [\"CITEREFRautenberg2010\"] = 1,\n [\"CITEREFReghizzi2009\"] = 1,\n}\ntemplate_list = table#1 {\n [\"About\"] = 1,\n [\"Authority control\"] = 1,\n [\"Cite book\"] = 5,\n [\"Cite journal\"] = 1,\n [\"Cite web\"] = 5,\n [\"DEFAULTSORT:Formal Language\"] = 1,\n [\"Expand section\"] = 1,\n [\"Formal languages\"] = 1,\n [\"Formal languages and grammars\"] = 1,\n [\"Harvtxt\"] = 1,\n [\"ISBN\"] = 4,\n [\"Main\"] = 3,\n [\"Mathematical logic\"] = 1,\n [\"More citations needed\"] = 1,\n [\"Mvar\"] = 14,\n [\"No\"] = 16,\n [\"NoteFoot\"] = 1,\n [\"NoteTag\"] = 1,\n [\"Refbegin\"] = 2,\n [\"Refend\"] = 2,\n [\"Reflist\"] = 1,\n [\"Short description\"] = 1,\n [\"Springer\"] = 1,\n [\"Use dmy dates\"] = 1,\n [\"Webarchive\"] = 1,\n [\"Yes\"] = 61,\n}\narticle_whitelist = table#1 {\n}\ntable#1 {\n [\"size\"] = \"tiny\",\n}\n"},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-26w6f","timestamp":"20241124162935","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Formal language","url":"https:\/\/en.wikipedia.org\/wiki\/Formal_language","sameAs":"http:\/\/www.wikidata.org\/entity\/Q192161","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q192161","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2001-08-27T00:41:01Z","dateModified":"2024-09-07T17:51:50Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/a\/aa\/Syntax_tree.svg","headline":"set of strings of symbols that may be constrained by rules that are specific to it; words whose letters are taken from an alphabet and are well-formed according to a specific set of rules"}</script> </body> </html>