UCPEL/ESIN/BCC

053218 Teoria da Computação

Programas, Máquinas e Computações.

Conteúdo:
Programas:
• Um conjunto de operações e testes compostos de acordo com uma estrutura
de controle:
o Monolíticos: desvios condicionais e incondicionais
o Iterativos: estruturas de iteração
o Recursivos: sub-rotinas recursivas

Máquina:
• Interpreta Programas
• Possui uma interpretação para cada operação ou teste que constituem o
programa.

Computação:
• Histórico do funcionamento da máquina para o programa e um dado valor
inicial.

Função Computada:
• Função parcial induzida a partir da máquina e programa dados, a qual é
definida sempre que, para um dado valor de entrada, existe uma
computação finita (a máquina pára).

Referências.

Programas
Um conjunto estruturado de instruções que capacitam uma máquina a aplicar
sucessivamente certas operações básicas e testes sobre os dados iniciais
fornecidos com o objetivo de transformar esses dados numa forma desejável.

• Operações e Testes:
o Operações: F, G, H...
o Testes: T1, T2, T3...
o Operação Vazia: √

Programa Monolítico
É estruturado com somente desvios condicionais e incondicionais. Não emprega
mecanismos auxiliares como iteração, sub-divisão ou recursão, de modo que toda a
lógica do programa esta contida em um único bloco: um monólito.

Fluxograma:
 test
partida parada operação
v e f

• Exercício 1: Usando apenas os símbolos de fluxograma acima, representar

um programa monolítico para calcular a soma dos 100 primeiros números
ímpares.

Instruções Rotuladas:
• Além da forma de um fluxograma, o programa pode ser representado como
uma seqüência de instruções rotuladas
• Exercício 2: Escrever o programa do exercício 1 como uma seqüência de
instruções rotuladas.

Definição: Rótulo, instrução rotulada.

• Um rótulo ou etiqueta é uma cadeia finita de caracteres constituída de letras
ou dígitos.
• Uma Instrução rotulada assume as formas:
o Operação: r1: faça F vá_para r2 ou r1: faça √ vá para r2.
o Teste: r1: se T então vá_para r2 senão vá_para r3.

Exemplo de Programa Monolítico:

1: faça F vá_para 2
2: se T1 então vá_para 1 senão vá_para 3
3: faça G vá_para 4
4: se T2 então vá_para 5 senão vá_para 1

Exercício 3: Fazer o fluxograma do Programa Monolítico acima

Definição: Programa Monolítico.

Um Programa Monolítico é um par P(I, r)
• I: Conjunto Finito de Instruções Rotuladas
• r: Rótulo inicial que distingue a instrução inicial em I
• Não existem duas instruções diferentes com o mesmo rótulo.
• Um rótulo não associado a nenhuma instrução é um rótulo final.
A estrutura oferecida pelos programas monolíticos é típica das linguagens de
máquinas e de programas montadores (assembly), entretanto isto se reflete de
diversas maneiras em linguagens de alto nível.

2.1.2 Programa Iterativo

• Substituem desvios incondicionais por estruturas cíclicas, permitindo um
melhor controle e manutenção de programas.
• A noção de programa iterativo deu origem às técnicas de programação
estruturada, inspirando toda uma geração de linguagens como Pascal.
 • São baseados em três mecanismos de composição de instruções,
encontrados em diversas linguagens: Algol 68, Pascal, Ada, Fortran 90, etc
o Seqüencial
o Condicional
o Enquanto (Até)

Definição: Programa Iterativo

Um programa Iterativo P é descrito indutivamente como se segue:
a. A operação vazia √ constitui um programa iterativo.
b. Cada identificador de operação constitui um programa iterativo.
c. Composição Seqüencial: Se V e W são programas iterativos, então a
composição seqüencial denotada por V;W é um programa iterativo, cujo
efeito é a execução de V e após de W.
d. Composição Condicional
e. Composição Enquanto
f. Composição Até
Parênteses podem ser empregados para mudar uma interpretação:
• (enquanto T faça V); W
• enquanto T faça (V; W)

Exemplo: Um programa iterativo

(se T1
então enquanto T2
faça (até T3 faça (V; W))
senão √)

Observações:
• É trivial traduzir um programa iterativo para um fluxograma, mas a recíproca
não é verdadeira.
• O uso de identação é interessante para facilitar o entendimento.

Exercício 4: Fazer o fluxograma do programa iterativo do exemplo acima.

Programa Recursivo

• Nas linguagens de programação em geral o conceito de programa recursivo

aparece associado ao de sub-rotinas recursivas.
• Recursão é uma forma indutiva de definir programas.
• Sub-rotinas permitem a estruturação hierárquica dos programas,
possibilitando níveis diferenciados de abstração.
Definição: Expressão de Sub-Rotinas
Uma Expressão de Sub-Rotinas, ou simplesmente Expressão é indutivamente
definida como se segue:
a. A operação vazia, √, constitui uma expressão de sub-rotinas.
b. Cada identificador de operação constitui uma expressão de sub-rotinas.
c. Cada identificador de sub-rotina constitui uma expressão de sub-rotinas.
d. Composição seqüencial: D1; D2
e. Composição condicional: (se T então D1 senão D2)

Definição: Programa Recursivo:

Um Programa Recursivo P tem a seguinte forma:
P é E0, onde R1 def E1, R2 def E2, ..., Rn def En
Onde, para k ∈ {1, 2, ..., n}

• E0 : Expressão Inicial, que é uma expressão de sub-rotinas.

• Ek : Expressão que define Rk, isto é, a expressão que define a sub-rotina

identificada por Rk
Adicionalmente, para cada identificador de sub-rotina referenciado em alguma
expressão, existe uma expressão que o define.
A operação vazia também é uma expressão de sub-rotinas

Raciocínio Recursivo:
• Lógica Recursiva.

• Pilha de Dados e Operações

Exemplo de Programa Recursivo:

P é R ; S, onde:
R def F; (se T então R senão G; S)
S def (se T então √ senão F; R)

Exemplos Concretos:
• Fatorial
• Fibonacci
• Lista Recursiva

Exercícios: Folha de Exercícios no. 1

2.2 Máquinas
• As máquinas interpretam os programas suprindo todos os recursos
necessários para realizar a computação que eles representam.
• Cada identificador de operação ou teste interpretado pela máquina deve ser
associado a uma transformação na estrutura da memória e a uma função
verdade respectivamente.
• Nem todo identificador de operação ou teste é definido em uma máquina.
• Para cada identificador de operação ou teste definido em uma máquina
existe somente uma função associada.
• Adicionalmente a máquina deve descrever o armazenamento ou
recuperação da informação na estrutura da memória.

Definição: Máquina.
Uma máquina é uma héptupla: M = ( V, X, Y, π X, π Y, Π F, Π T ), onde:
• V – Conjunto de Valores de Memória
• X – Conjunto de Valores de Entrada
• Y – Conjunto de Valores de Saída

• π X – Função de Entrada, tal que π X: X  V

• π Y – Função de Saída, tal que π Y: V  Y

• Π F – Conjunto de Interpretações de Operações.

Para cada F existe uma única π F: V V

• Π T – Conjunto de Interpretações de Testes.

Para cada T existe uma única π T: V {verdadeiro, falso}
Os conjuntos de interpretações podem ser vistos como conjuntos de funções,
indexadas pelo subconjunto de identificadores de operações e testes para os quais
a máquina está definida.

Exemplo: Máquina de Dois Registradores:

Seja uma máquina com dois registradores, a e b, que assumem valores em N, com
duas operações e um teste:
• Subtrair 1 de a, se a > 0.
• Adicionar 1 em b.
• Teste se a é zero.
Adicionalmente Valores de Entrada são armazenados em a (zerando b) e a Saída
retorna o valor de b.
Implementação:
dois_reg = ( N2, N, N, armazena_a, retorna_b, {subtrai_a, adiciona_b}, {a_zero} ),
onde:

• V = N2 = Conjunto de Valores de Memória.

• X = N = Conjunto de Valores de Entrada
• Y = N = Conjunto dos Valores de Saída

• armazena_a: N  N2, tal que, para todo n ∈ N, armazena_a(n) = (n, 0)

 • retorna_b: N2  N tal que, para todo n ∈ N, retorna_b(n, m) = m

• subtrai_a: N2  N2 tal que, para todo (n, m) ∈ N2,

o subtrai_a(n, m) = (n-1, m), se n ≠ 0,
o subtrai_a(n, m) = (0, m), se n = 0.

• adiciona_b: N2  N2 tal que, para todo (n, m) ∈ N2, adiciona_b(n, m) = (n,

m+1)

• a_zero: N2  {verdadeiro, falso}, tal que, para todo (n, m) ∈ N2,

o a_zero(n, m) = verdadeiro, se n = 0,
o a_zero(n, m) = falso, se n ≠ 0,

Definição: Programa para uma Máquina.

Diz-se que P é um programa para a máquina M se cada operação e teste em P
corresponder a uma interpretação em M.
Formalmente:
Seja M = ( V, X, Y, π X, π Y, Π F, Π T ), uma máquina e P um programa onde PF e PT são
conjuntos de operações e testes de P. P é um programa para a máquina M se e
somente se:

• Para toda F em PF, existe uma única função π F: V V em Π F.

• Para todo T em PT, existe uma única função π T: V V em Π T.

• A operação vazia, √, é interpretada em qualquer máquina.

2.3 Computações e Funções Computadas

Uma computação de um programa monolítico em uma máquina é um histórico de
instruções executadas e o correspondente valor de memória. O histórico é
representado como uma cadeia de pares onde:

• Cada par reflete um estado de máquina para o programa, ou seja, a função a

ser executada e o valor corrente de memória.
• A cadeia reflete uma seqüência de estados possíveis a partir do estado
inicial. (instrução inicial e valor de memória considerado).

Definição: Computação de um Programa Monolítico em uma Máquina.

Seja M = ( V, X, Y, π X, π Y, Π F, Π T ), uma máquina e P = (I, r) um programa
monolítico para M, onde L é o seu correspondente conjunto de rótulos. Uma
computação do programa monolítico P para a máquina M é uma cadeia (finita ou
infinita) de pares de LxV (s0,v0)(s1,v1)(s2,v2)... onde os sk são os rótulos de instruções
e os vk os correspondentes estados da memória.
Seja F um identificador de operação, T um identificador de teste e r’ e r” rótulos de
L.

• Operação:
a. Se sk é o rótulo de uma operação da forma sk: faça F vá_para r’
então (sk+1, vk+1 ) = (r’, π F(vk)) é par subseqüente de (sk, vk) na
cadeia.
 b. Se sk é o rótulo de uma operação da forma sk: faça √ vá_para r’,
então (sk+1, vk+1 ) = (r’, vk) é par subseqüente de (sk, vk) na cadeia.

• Teste:

• Se sk é o rótulo de um teste da forma sk: Se T então vá_para r’

senão vá_para r”, então (sk+1, vk+1 ) é par subseqüente de (sk, vk) na
cadeia , sendo que vk+1 = vk e:
i. sk+1 = r’ se π T(vk) = verdadeiro
ii. sk+1 = r” se π T(vk) = falso

Observações:
• A computação pode ser finita ou infinita, conforme a cadeia for finita ou
infinita.

• Para um dado valor inicial de memória, a correspondente cadeia de

computação é única, ou seja, a computação é determinística. Por que?
• Um teste e a operação vazia não alteram o conteúdo de memória.
• Em uma computação infinita não há rótulo final.
Exemplo:
Computação Finita de Programa Monolítico na Máquina de Dois
Registradores
1: Se a_zero então vá_para 9 senão vá_para 2.
2: faça subtrai_a vá_para 3.
3: faça adiciona_b vá_para 1.

(sk, vk) Ação

(1,(3,0)) Instrução inicial e valor de entrada armazenado.
(2,(3,0)) Em 1, como a≠ 0, desviou para 2.
(3,(2,0)) Em 2, subtraiu 1 do registrador a e desviou para 3.
(1,(2,1)) Em 3, adicionou 1 ao valor de b e desviou para 1,
(2,(2,1)) Em 1, como a≠ 0, desviou para 2.
(3,(1,1)) Em 2, subtraiu 1 do registrador a e desviou para 3.
(1,(1,2)) Em 3, adicionou 1 ao valor de b e desviou para 1,
(2,(1,2)) Em 1, como a≠ 0, desviou para 2.
(3,(0.2)) Em 2, subtraiu 1 do registrador a e desviou para 3.
(1,(0,3)) Em 3, adicionou 1 ao valor de b e desviou para 1,
(9,(0,3)) Em 1, como a=0, desviou para 9.

Definição: Computação de um Programa Recursivo em uma Máquina

Seja M = ( V, X, Y, π X, π Y, Π F, Π T ), uma máquina e P um programa recursivo para
M, tal que:
P é E0 onde R1 def E1, R2 def E2, ..., Rn def Em.
Uma computação do programa recursivo P na máquina M é uma cadeia (finita ou
infinita) de pares da forma:
 (D0, v0)(D1, v1)(D2, v2)...
onde (D0, v0) é tal que D0 = E0;√ e v0 é o valor inicial da máquina.
Para cada par (Dk, vk), supondo que F é um identificador de operação, T é um
identificador de teste e C, C1 e C2 são expressões de sub-rotinas:

• Caso 1: Dk = √; C  (Dk+1, vk+1) = (C, vk) é par subseqüente de (Dk, vk) na

cadeia.

• Caso 2: Dk = F; C  (Dk+1, vk+1) = (C, π F(vk)) é par subseqüente de (Dk,

vk) na cadeia.

• Caso 3: Dk = Ri; C  (Dk+1, vk+1) = (Ei;C, vk) é par subseqüente de (Dk, vk)
na cadeia.

• Caso 4: Dk = (C1; C2); C  (Dk+1, vk+1) = (C1;(C2;C), vk) é par subseqüente

de (Dk, vk) na cadeia.

• Caso 5: Dk = Ek = (Se T então C1 senão C2); C  (Dk+1, vk+1) é par

subseqüente de (Dk, vk) na cadeia, sendo que:
o Vk+1 = vk
o Dk+1 = C1; C se π T(vk) é verdadeiro
o Dk+1 = C2; C se π T(vk) é falso

Observações:

• A computação pode ser finita ou infinita conforme a cadeia for finita ou

infinita.
• A computação é determinística (por quê?)
• Teste ou referência a uma sub-rotina não alteram o valor da memória.

• Em uma computação finita, a expressão vazia ocorre no último par da cadeia

e não ocorre em nenhum outro par.

• Em uma computação infinita, a expressão vazia não ocorre em nenhum par.

Função Computada
Noção Intuitiva (programa monolítico):
• A computação inicia na instrução identificada pelo rótulo inicial com a
memória contendo o valor inicial resultante da aplicação da função de
entrada sobre o dado fornecido.

• Executa, passo a passo, testes e operações na ordem determinada pelo

programa, até atingir um rótulo final, quando pára.

• O valor da função computada pelo programa é o valor resultante da

aplicação da função de saída ao valor da memória quando da parada.

Definição: Função Computada por um Programa Monolítico em uma

Máquina
Seja M = ( V, X, Y, π X, π Y, Π F, Π T ), uma máquina e P = (I, r) um programa
monolítico para M. A função computada pelo programa monolítico P na máquina M,
denotada por <P,M>: X  Y é uma função parcial definida para x∈X se a cadeia
(s0,v0)(s1,v1)...(sn,vn) é uma computação finita de P em M, onde o valor inicial da
memória é dado pela função de entrada, ou seja, v0 = π X(X). Neste caso a imagem
de x é dada pela função de saída aplicada ao último valor da memória na
computação, ou seja: <P,M>(x) = π Y(vn).
• Note-se que a função computada pode ser parcial, isto é, não está definida
para todos os valores do domínio.

Exemplo: Função Computada por um Programa Monolítico na Máquina de

Dois Registradores.
Considere o programa monolítico mon_ba para a máquina dois_reg:
1: Se a_zero então vá_para 9 senão vá_para 2.
2: faça subtrai_a vá_para 3.
3: faça adiciona_b vá_para 1.
dois_reg = ( N2, N, N, armazena_a, retorna_b, {subtrai_a, adiciona_b}, {a_zero} ),
A correspondente função computada é a função identidade, ou seja:
<mon_ba, dois_reg>: N  N
tal que, para qualquer n∈N, tem-se que <mon_ba, dois_reg>(n) = n

Noção Intuitiva (programa recursivo)

• A computação inicia na instrução identificada pelo rótulo inicial com a
memória contendo o valor inicial resultante da aplicação da função de
entrada sobre o dado fornecido.
• Executa, passo a passo, testes e operações na ordem determinada pelo
programa, até que a expressão de sub-rotina resultante seja a expressão
vazia, quando pára.
• O valor da função computada pelo programa é o valor resultante da
aplicação da função de saída ao valor da memória quando da parada.

Definição: Função Computada por um Programa Recursivo em uma

Máquina

Seja M = ( V, X, Y, π X, π Y, Π F, Π T ), uma máquina e P um programa recursivo para

M. A função computada pelo programa recursivo P na máquina M, denotada por
<P,M>: X  Y é uma função parcial definida para x∈X se a cadeia (D0,v0)(D1,v1)...
(Dn,vn) é uma computação finita de P em M, onde

• D0 = E0;√ é expressão inicial de P

• v0 = π X(X)
• En = √
Neste caso a imagem de x é dada pela função de saída aplicada ao último valor da
memória na computação, ou seja: <P,M>(x) = π Y(vn).

Exercício: Definir função computada por um programa iterativo P em uma

máquina M.
2.4 Equivalência de Programas e Máquinas
Funções computadas permitem introduzir importantes relações de equivalência
entre programas e máquinas:

• Relação de Equivalência Forte de Programas: Um par de programas

pertence à relação se as correspondentes funções computadas coincidem
para qualquer máquina.

• Relação Equivalência de Programas em uma Máquina: Um par de

programas pertence à relação se as correspondentes funções computadas
coincidem para uma dada máquina.

• Relação Equivalência de Máquinas: Um par de máquinas pertence à

relação se as máquinas podem se simular mutuamente.

A relação Equivalência Forte de programas é especialmente importante, pois:

• Permite agrupar diferentes programas em classes de equivalência de

programas cujas funções coincidem.
• Fornece subsídios para analisar propriedades de programas como a
complexidade estrutural.

Definição: Igualdade de Funções Parciais.

Duas funções parciais, f, g:XY são ditas iguais, ou seja, f = g, se e somente se,
para cada x∈X (1) ou f e g são indefinidas, ou ambas são definidas com f(x)=g(x).

Definição: Composição Sucessiva de Funções.

Para uma dada função f:SS, a composição sucessiva de f com ela própria é
denotada usando expoente, ou seja, fn = f ° f °...° f (n vezes).

2.4.1 Equivalência Forte de Programas

Def: Relação Equivalência Forte de Programas. Programas Fortemente

Equivalentes.
Sejam P e Q dois programas arbitrários, não necessariamente do mesmo tipo, então
o par (P, Q) está na Relação de Equivalência Forte de Programas, denotado por
P≡ Q, se e somente se, para qualquer máquina M as correspondentes funções
computadas são iguais, isto é: <P,M> = <Q,M>.
Neste caso, P e Q são ditos Programas Equivalentes Fortemente.

Exercício: Mostrar que a Relação Equivalência Forte de Programas é uma relação

de equivalência, e que portanto induz uma partição do conjunto de todos os
programas em classes de equivalências.

Exemplo: Programas Equivalentes Fortemente:

P3: enquanto T faça (F)
P4 é R onde R def (se T então F;R senão √)

Razões para Considerar a Equivalência Forte de Programas:

• Permite identificar diferentes programas em uma mesma classe de

equivalência, ou seja identificar diferentes programas cujas funções
computadas coincidem para qualquer máquina.
• As funções computadas por programas equivalentes tem a propriedade de
que as mesmas operações são efetuadas na mesma ordem,
independentemente do significado dos mesmos (por quê?)
• Fornece subsídios para analisar a complexidade estrutural de programas.

Verifica-se que:
• Para todo iterativo, existe um monolítico equivalente fortemente.
• Para todo monolítico, há um recursivo equivalente fortemente.

• Iterativos ⊆ Monolíticos ⊆ Recursivos. (Teoremas 2.14 a 2.18)

2.4.2 Equivalência de Programas

Definição: Relação Equivalência de Programas em uma Máquina.

Sejam P e Q dois programas arbitrários, não necessariamente do mesmo tipo, e

uma máquina M qualquer. Então o par (P, Q) está na Relação Equivalência de
Programas na Máquina M, denotado por P≡ MQ, se e somente se as correspondentes
funções computadas são iguais, ou seja, <P,M> = <Q,M>.

Neste caso, P e Q são ditos Programas Equivalentes na Máquina M, ou

simplesmente Programas M-Equivalentes.

2.4.3 Equivalência de Máquinas

Afirma-se que duas máquinas são equivalentes, se uma pode simular a outra e vice-
versa.

Definição: Simulação Forte de Máquina.

Sejam M = ( VM, X, Y, π XM, π YM, Π FM, Π TM ), e N = ( VN, X, Y, π XN, π YN, Π FN, Π TN ),

duas máquinas arbitrárias. N simula fortemente M se e somente se para qualquer
programa P para M existe um programa Q para N tais que as correspondentes
funções parciais computadas coincidem, ou seja, <P,M>=<Q,N>

Definição: Simulação de Máquina.

Sejam M = ( VM, X, Y, π XM, π YM, Π FM, Π TM ), e N = ( VN, X, Y, π XN, π YN, Π FN, Π TN ),

duas máquinas arbitrárias. N simula M se e somente se para qualquer programa P
para M existe um programa Q para N e existem

• Função de Codificação c:XMXN

• Função de Decodificação d:YNYM

tais que <P,M>= d °<Q,N>° c

Definição: Relação Equivalência de Máquinas.

Sejam M e N duas máquinas arbitrárias, então o par (N, M) está na Relação

Equivalência de Máquina se e somente se M simula N e N simula M.

2.5 Verificação da Equivalência Forte de Programas

• Não há algoritmos para os programas recursivos.
• Mas há algoritmos para programas monolíticos (e, portanto, também para os
iterativos)

Conceitos Importantes:

• Máquina de Traços: Produz um rastro ou histórico (denominado traço) da

ocorrência das operações do programa.

• Programa Monolítico com Instruções Rotuladas Compostas: São

programas que contém instruções do tipo:
r1: se T então faça F vá_para r2 senão faça G vá_para r3

2.5.1 Máquina de Traços

• Não executa as operações propriamente ditas,

• Produz apenas um histórico, rastro ou traço da ocorrência destas,
• Portanto em computações finitas o traço é uma palavra sobre um alfabeto
de identificadores de operações.
• Se dois programas são equivalentes em qualquer máquina de traços, então
eles são fortemente equivalentes.
• A noção de traço também é importante no estudo da concorrência e de
semântica formal.
Definição: Máquina de Traços.
Uma Máquina de Traços é uma máquina:
M = (Op*, Op*, Op*, idOp, idOp, Π F, Π T)
Onde:
Op* = Conjunto de palavras de operações, onde Op = {F, G, ...} o qual
corresponde simultaneamente ao conjuntos de valores de memória, entrada
e saída.
IdOp = Função Identidade em Op* a qual corresponde simultaneamente às
funções de entrada e saída.
Π F = Conjunto de Interpretações de operações onde, para cada identificador
de operação F de Op, a interpretação π F:OpOp é tal que para qualquer
w∈Op* π F(w) resulta na concatenação do identificador F à direita de w, ou
seja π F(w)=wF.
Π T = Conjunto de Interpretação de testes, tal que para cada identificador de
teste T, π T:Op*{verdadeiro, falso} é função de Π T.
Portanto o efeito de cada operação interpretada por uma máquina de traços é
simplesmente acrescentar o identificador de operação à direita do valor atual da
memória. O valor de saída da função composta consiste em um histórico das
operações executadas durante a computação.

Definição: Função Induzida por um Traço em uma Máquina.

Seja M = ( V, X, Y, π X, π Y, Π F, Π T ), uma máquina, Op = {F, G, H, ...} o conjunto de
operações interpretadas em Π F e w=FG...H um traço possível de M, isto é, w∈Op*.
A Função Induzida pelo Traço w na Máquina M, denotada por [w, M]:XV é a função
(total):
[w, M] = π H°...°π G°π F°π X.
Portanto a função induzida por um traço nada mais é do que a função resultante da
composição das interpretações das diversas operações que constituem o traço.
Notar ainda que a composição de funções é notada na ordem inversa à
concatenação de símbolos no traço

Teorema:
Sejam P e Q dois programas arbitrários não necessariamente do mesmo tipo. Então
P≡ Q se e somente se, para qualquer máquina de traços M, P≡ MQ.

Instruções Rotuladas Compostas.

• Possuem somente uma única forma, combinando operações e testes.

Definição: Instrução Rotulada Composta (IRC)

Uma IRC é uma seqüência de símbolos da seguinte forma:
 R1: se T então faça F vá_para r2 senão faça G vá_para r3

• r2 e r3 são ditos rótulos sucessores de r1.

• r1 é dito rótulo antecessor de r2 e r3.

Definição: Programa Monolítico com Instruções Rotuladas Compostas

Um Programa Monolítico com Instruções Rotuladas Compostas P é um par P = (I, r),
onde:
I - Conjunto finito de Instruções Rotuladas Compostas
r – Rótulo Inicial, que distingue a Instrução Rotulada Inicial em I
Adicionalmente, em relação ao conjunto I tem-se:
• Não existem duas instruções diferentes com o mesmo rótulo.

• Um rótulo referenciado por alguma instrução sem correspondente em

qualquer outra instrução rotulada é dito um Rótulo Final.

Algoritmo: Fluxograma  Instruções Rotuladas Compostas

• Os componentes elementares de um fluxograma (partida, parada e
operação) são genericamente denominados de nó.

O Algoritmo para traduzir um fluxograma P para um programa monolítico P´

constituídos por instruções rotuladas compostas é como se segue:

a. Rotulação de Nós:
i. Rotula-se cada nó do fluxograma.
ii. Supõe-se, sem perda de generalidade, que existe um único
componente elementar de parada, ao qual é atribuída a
palavra vazia.
iii. O rótulo correspondente ao nó partida é o rótulo inicial do
programa P´
b. Instruções Rotuladas Compostas (IRC): A construção de uma IRC
inicia no nó partida e segue o caminho do fluxograma. Dependendo
do próximo componente elementar tem-se que

i. Teste: r1: (F, r2), (G, r3)

ii. Operação: r1: (F, r2), (F, r2)

 iii. Parada: r: (parada, ε ), (parada, ε )

iv. Testes Encadeados:

r1: (F, r2), (G, r3)

v. Testes Encadeados em Ciclo Infinito:

r1: (F, r2), (ciclo, ω )
Neste caso deve ser incluída
adicionalmente uma IRC
correspondente ao ciclo infinito,
ou seja: ω : (ciclo, ω ), (ciclo, ω ).

Exemplo: Fluxograma  Rotuladas Compostas

Rótul Té T é Falso
o Verdadeiro
1: (G, 2) (F, 3)
2: (G, 2) (F, 3)
3: (F, 4) (G, 5)
4: (F, 4) (G, 5)
5: (F, 6) (ciclo, ω )
6: (parada, ε ) (G, 7)
7: (G, 7) (G, 7)
ω: (ciclo, ω ) (ciclo, ω )