Posts Tagged ‘formal-grammar’

Apunts de Teoria de la Computació: Gramàtiques incontextuals

Una gramàtica incontextual (CFG, Context Free Grammar) [latex]G[/latex] és un conjunt de regles de substitució on les parts esquerres són mots de longitud 1. Aquestes regles les anomenarem produccions i les seves parts esquerres variables (o no-terminals). Els símbols restants els anomenem terminals. Dues regles com per exemple [latex]S \rightarrow aS[/latex] i [latex]S \rightarrow X[/latex] […]

Apunts de Teoria de la Computació: Teoria de llenguatges

Un alfabet ([latex]\Sigma[/latex]) és un conjunt finit d’elements (símbols), habitualment caràcters alfanumèrics. Un mot és una llista de símbols d’un alfabet. El mot buit (llista de longitud 0) el denotarem amb el meta-símbol [latex]\lambda[/latex]. Utilitzarem [latex]u[/latex], [latex]v[/latex], [latex]w[/latex], [latex]u_1[/latex], … per denominar paraules. [latex]\Sigma = \{a, b\}[/latex] Paraules: ab, bbb, a, [latex]\lambda[/latex] Longituds: |ab|=2, |bbb|=3, […]

 
Skip to toolbar