<?xml version="1.0" encoding="UTF-8"?>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:wx="http://ilps.science.uva.nl/WikiXML/wx" xml:lang="it" lang="it">
<head>
<title>Parola di Dyck</title>
<meta name="wx_namespace" content="0"/>
<meta name="wx_pagename" content="Parola_di_Dyck"/>
<meta name="wx_page_id" content="348199"/>
</head>
<body>
<div id="wx_article">
<wx:section level="1" title="Parola di Dyck" id="wxsec1"><h1 class="pagetitle" id="wx1">Parola di Dyck</h1>

<wx:template id="wx_t1" pagename="Template:S" page_id="473933"/>
<div class="toccolours itwiki_template_avviso rad noprint" style="margin-bottom:.5em" id="wx2">
<div style="align:left; margin:-3px 0 -4px" id="wx3"><a href="/wit/Immagine:Stub_matematica.png" title="Stub" wx:linktype="image" wx:pagename="Immagine:Stub_matematica.png" wx:page_id="627197" id="wx4"><img src="/wit/Immagine:Stub_matematica.png" alt="Stub" width="30" id="wx5"/></a>
<p id="wx6"> Questa voce di <a href="/wit/Matematica" title="Matematica" wx:linktype="known" wx:pagename="Matematica" wx:page_id="2708" id="wx7">matematica</a> è solo un <a href="/wit/Aiuto:Abbozzo" title="Aiuto:Abbozzo" wx:linktype="known" wx:pagename="Aiuto:Abbozzo" id="wx8">abbozzo</a>: <b id="wx9"><a href="http://wit/wit/index.php?title=Parola_di_Dyck&amp;action=edit" class="external text" wx:linktype="external" rel="nofollow" id="wx10">contribuisci</a></b> a migliorarla secondo le <a href="/wit/Aiuto:Manuale_di_stile" title="Aiuto:Manuale di stile" wx:linktype="known" wx:pagename="Aiuto:Manuale_di_stile" id="wx11">convenzioni di Wikipedia</a>.</p>
</div>
</div>

<wx:templateend start="wx_t1"/>
<p id="wx12">Nella <a href="/wit/Teoria_dei_linguaggi_formali" title="Teoria dei linguaggi formali" wx:linktype="known" wx:pagename="Teoria_dei_linguaggi_formali" wx:page_id="4341" id="wx13">teoria dei linguaggi formali</a>, una <b id="wx14">parola di Dyck</b> è una <a href="/wit/Stringa_%28formale%29" title="Stringa (formale)" wx:linktype="known" wx:pagename="Stringa_(formale)" wx:page_id="79896" id="wx15">stringa</a> consistente di <i id="wx16">n</i> simboli X ed <i id="wx17">n</i> simboli Y tale che, preso comunque un segmento iniziale della stringa, esso non contenga più simboli Y che simboli X.</p>

<p id="wx18">Ad esempio, le parole di Dyck di lunghezza 6 sono:</p>

<table style="width:70%;left:15%;position:relative;font-size:larger;text-align:center;" id="wx19">
<tr id="wx20">
<td id="wx21">
<p id="wx22">XXXYYY</p>
</td>
<td id="wx23">
<p id="wx24">XYXXYY</p>
</td>
<td id="wx25">
<p id="wx26">XYXYXY</p>
</td>
<td id="wx27">
<p id="wx28">XXYYXY</p>
</td>
<td id="wx29">
<p id="wx30">XXYXYY</p>
</td>
</tr>
</table>

<p id="wx31">mentre invece queste <b id="wx32">non</b> lo sono:</p>

<table style="width:70%;left:15%;position:relative;font-size:larger;text-align:center;" id="wx33">
<tr id="wx34">
<td id="wx35">
<p id="wx36">YYYXXX</p>
</td>
<td id="wx37">
<p id="wx38">YXYYXX</p>
</td>
<td id="wx39">
<p id="wx40">YXYXYX</p>
</td>
<td id="wx41">
<p id="wx42">YYXXYX</p>
</td>
<td id="wx43">
<p id="wx44">YYXYXX</p>
</td>
</tr>
</table>

<p id="wx45">Definendo il simbolo X come la parentesi aperta ed il simbolo Y come la parentesi chiusa, allora una parola di Dyck corrisponde ad un insieme di parentesi che sono disposte in maniera completa (ad ogni parentesi aperta ne corrisponde una chiusa) e logicamente coerente (le parentesi sono correttamente annidate e non vi è mai una parentesi chiusa senza che prima ci sia la relativa parentesi aperta). Con questa definizione, la serie delle parole di Dyck di lunghezza 6 diventa:</p>

<table style="width:70%;left:15%;position:relative;font-size:larger;text-align:center;" id="wx46">
<tr id="wx47">
<td id="wx48">
<p id="wx49">((()))</p>
</td>
<td id="wx50">
<p id="wx51">()(())</p>
</td>
<td id="wx52">
<p id="wx53">()()()</p>
</td>
<td id="wx54">
<p id="wx55">(())()</p>
</td>
<td id="wx56">
<p id="wx57">(()())</p>
</td>
</tr>
</table>

<p id="wx58">Il numero delle parole di Dyck aventi lunghezza <i id="wx59">2n</i> (com'è stato provato da D. André nel <a href="/wit/1887" title="1887" wx:linktype="known" wx:pagename="1887" wx:page_id="4865" id="wx60">1887</a>) corrisponde all'<i id="wx61">n</i>-esimo <a href="/wit/Numero_di_Catalan" title="Numero di Catalan" wx:linktype="known" wx:pagename="Numero_di_Catalan" wx:page_id="51626" id="wx62">numero di Catalan</a>.</p>
</wx:section></div>
<div id="wx_categorylinks">
<a href="/wit/index.php?title=Speciale:Categories&amp;article=Parola_di_Dyck" title="Speciale:Categories" wx:linktype="known" wx:pagename="Speciale:Categories" id="wx63">Categorie</a>: <span dir="ltr" id="wx64"><a href="/wit/Categoria:Stub_matematica" title="Categoria:Stub matematica" wx:linktype="known" wx:pagename="Categoria:Stub_matematica" wx:page_id="225971" id="wx65">Stub matematica</a></span> | <span dir="ltr" id="wx66"><a href="/wit/Categoria:Linguaggi_formali" title="Categoria:Linguaggi formali" wx:linktype="known" wx:pagename="Categoria:Linguaggi_formali" wx:page_id="42408" id="wx67">Linguaggi formali</a></span></div>
<div id="wx_languagelinks">
</div>
</body>
<wx:templatearguments for="wx_t1"><wx:argument name="1">
<p id="wx68">matematica</p>
</wx:argument></wx:templatearguments>
</html>
