Símbolos e Notação

Símbolos e notação usados no vault

Voltar ao mapa · Veja também o Glossário.

Esta nota explica todos os símbolos que aparecem nas notas, com o jeito de ler em voz alta, o significado e um exemplo tirado da matéria. Levantei a lista varrendo os arquivos do vault, então se um símbolo aparece em alguma nota, ele está aqui.

Os 12 que mais aparecem

Se for decorar só alguns, comece por estes: $\epsilon$ (palavra vazia), $\Sigma$ ou $V$ (alfabeto), ${}^{\ast }$ (zero ou mais), ${}^{+}$ (uma ou mais), $\mid$ (“tal que” ou “ou”, depende do lugar), $\in$ (pertence), $\cup$ (união), $\varnothing$ (conjunto vazio), $\times$ (produto cartesiano), $\to$ (função ou produção), $\Rightarrow$ (derivação ou implicação), $\delta$ ou $T$ (função de transição).

1. Letras gregas

Símbolo	Nome	Para que é usado aqui
$\alpha ,\beta ,\gamma$	alfa, beta, gama	cadeias quaisquer (de terminais e não terminais) em gramáticas; expressões regulares genéricas em 03b
$\delta$	delta	função de transição do autômato, na notação dos livros (nos slides é $T$)
$\hat{\delta }$	delta chapéu	função de transição estendida: processa uma palavra inteira, não só um símbolo
$\epsilon$	épsilon	a palavra vazia, com zero símbolos. Também rotula a transição vazia
$\Sigma$	sigma maiúsculo	o alfabeto nos livros (nos slides é $V$ ou $V_t$)
$\Pi$	pi maiúsculo	uma partição (família de blocos) em 02 - Matemática Discreta

Não confunda $\epsilon$ com $\varnothing$ e $\{\epsilon \}$

• $\epsilon$ é uma palavra (a vazia). $|\epsilon |=0$.
• $\varnothing$ é uma linguagem sem nenhuma palavra.
• $\{\epsilon \}$ é uma linguagem com exatamente uma palavra, a vazia.

Um autômato que aceita $\varnothing$ não aceita nada. Um que aceita $\{\epsilon \}$ aceita só a entrada vazia.

2. Conjuntos

Símbolo	Lê-se	Significado	Exemplo
$\{\}$	conjunto	lista os elementos, sem ordem e sem repetição	$\{a,b\}$
$\{x\mid P(x)\}$	”o conjunto dos $x$ tal que $P(x)$“	define um conjunto por uma propriedade. Aqui a barra significa tal que	$\{w\in \{a,b{\}}^{\ast }\mid |w|\text{ eˊ par}\}$
$\in$	pertence a	o elemento está no conjunto	$ab\in \{a,b{\}}^{\ast }$
$\notin$	não pertence a	o elemento não está no conjunto	$ba\notin a^{\ast }{b}^{\ast }$
$\ni$	contém (o elemento)	o mesmo que $\in$ lido ao contrário: $A\ni x$ é $x\in A$	$T(X,a)\ni Y$: $Y$ está entre os destinos
$\subseteq$	está contido ou é igual	todo elemento de um está no outro	$L\subseteq V^{\ast }$
$\subset$	está contido estritamente	contido e diferente	Tipo 3 $\subset$ Tipo 2
$\cup$	união	elementos que estão em um ou no outro	$\{a\}\cup \{b\}=\{a,b\}$
$\cap$	interseção	elementos que estão nos dois	$L_1\cap L_2$
${\bigcup }_{q\in P}$	união de todos os …	união de uma família inteira de conjuntos	${\bigcup }_{q\in P}\delta (q,a)$: junta os destinos de todos os estados ativos
$A-B$	$A$ menos $B$	diferença: o que está em $A$ e não em $B$	$V^{+}=V^{\ast }-\{\epsilon \}$
$\overline{L}$	complemento de $L$	tudo que não está em $L$ (dentro de ${\Sigma }^{\ast }$)	$\overline{L}={\Sigma }^{\ast }-L$
$\varnothing$	conjunto vazio	conjunto sem elementos	${\varnothing }^{\ast }=\{\epsilon \}$
$A\times B$	$A$ cartesiano $B$	todos os pares ordenados $(a,b)$	$K\times V$: pares (estado, símbolo)
$(a,b)$	par ordenado	a ordem importa: $(a,b)\ne (b,a)$	$(q,a)$ na tabela de transição
$2^A$	partes de $A$	o conjunto de todos os subconjuntos de $A$ (se $A$ tem $n$ elementos, são $2^n$)	$2^K$: os conjuntos de estados de um AFND
$|A|$	cardinalidade de $A$	número de elementos	$|A\times B|=|A|\cdot |B|$
$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$	combinação de $n$, $k$ a $k$	quantos subconjuntos de $k$ elementos um conjunto de $n$ tem	$\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$

Sobre $\subset$

Nas notas, $\subset$ sempre indica inclusão estrita (por exemplo, toda linguagem regular é livre de contexto, mas não o contrário). Alguns autores usam $\subset$ no sentido de $\subseteq$. Se aparecer num livro ou prova, confira o sentido pelo contexto.

Conjuntos numéricos

Símbolo	Nome	Conteúdo
$\mathbb{N}$	naturais	$\{0,1,2,3,\dots \}$. Nas notas o 0 está incluído, como nos exemplos dos livros
$\mathbb{Z}$	inteiros	$\{\dots ,-2,-1,0,1,2,\dots \}$
$\mathbb{Q}$	racionais	frações $p/q$ com $q\ne 0$
$\mathbb{R}$	reais	racionais mais irracionais, como $\sqrt{2}$

3. Lógica, relações e funções

Símbolo	Lê-se	Significado	Exemplo
$\Rightarrow$	implica	”se … então …” (em 02 - Matemática Discreta)	$\neg q\Rightarrow \neg p$
$⟺$ ou ⟺	se e somente se	as duas afirmações são verdadeiras juntas ou falsas juntas	o AFD aceita $w$ ⟺ o AFND aceita $w$
$\neg$	não	negação	$\neg p$
$\exists$	existe	há pelo menos um	$\exists y,(x,y)\in R$
$=,\ne$	igual, diferente		$(a,b)\ne (b,a)$
$\le ,\ge$	menor ou igual, maior ou igual		$|uv|\le n$
$\equiv$	equivalente	depende do contexto, veja a seção 10	$4\equiv 0(\mathrm{mod}4)$
$\mathrm{mod}$	módulo	resto da divisão	$(\#a-\#b)\mathrm{mod}4$
$f:A\to B$	$f$ de $A$ em $B$	função com domínio $A$ e codomínio $B$	$T:K\times V\to K$
$x\mapsto y$	$x$ vai em $y$	diz o que a função faz com cada elemento	$n\mapsto n+1$
$g\circ f$	$g$ composta com $f$	aplicar uma função e depois a outra. A ordem muda conforme a fonte: veja 02 - Matemática Discreta	Menezes: $(g\circ f)(a)=g(f(a))$
$R^{\ast }$	fecho reflexivo-transitivo	”zero ou mais passos” da relação $R$	${⊢}^{\ast }$, ${\Rightarrow }^{\ast }$
$R^{+}$	fecho transitivo	”um ou mais passos”	${\Rightarrow }^{+}$
$\sqrt{2}$	raiz de dois	aparece só como exemplo de prova por contradição
$\cdot$	vezes	multiplicação	$m\cdot n$ transições

4. Palavras e linguagens

Símbolo	Lê-se	Significado	Exemplo
$V$, $V_t$, $\Sigma$	alfabeto	conjunto finito de símbolos	$\Sigma =\{a,b\}$
$w$, $u$, $v$, $x$, $y$, $z$	palavra	letras usadas para nomear palavras (cadeias)	$w=abba$
$uv$	$u$ concatenado com $v$	escrever uma palavra colada na outra	$u=ab,v=ba\Rightarrow uv=abba$
$|w|$	tamanho de $w$	número de símbolos	$|abba|=4$
$\#a(w)$ ou $\#a$	número de $a$ em $w$	quantas vezes o símbolo $a$ aparece	$\#a(abba)=2$
$a^n$	$a$ elevado a $n$	o símbolo $a$ repetido $n$ vezes	$a^3=aaa$, $a^0=\epsilon$
$w^n$	$w$ elevado a $n$	a palavra repetida $n$ vezes	$(ab{)}^2=abab$
$w^R$	reverso de $w$	a palavra de trás para frente	$(abc{)}^R=cba$
$V^{\ast }$, ${\Sigma }^{\ast }$	fecho de Kleene	todas as palavras sobre o alfabeto, incluindo $\epsilon$	$\{a{\}}^{\ast }=\{\epsilon ,a,aa,\dots \}$
$V^{+}$, ${\Sigma }^{+}$	fecho positivo	todas as palavras, sem $\epsilon$	$\{a{\}}^{+}=\{a,aa,\dots \}$
$L$, $L_1$, $L_2$	linguagem	um conjunto de palavras, $L\subseteq {\Sigma }^{\ast }$	$L=\{a^n{b}^n\mid n\ge 0\}$
$L^{\ast }$, $L^{+}$	fecho da linguagem	concatenações de zero (ou uma) ou mais palavras de $L$	se $\epsilon \in L$, então $L^{+}=L^{\ast }$
$L(M)$, $L(G)$	linguagem de $M$ ou de $G$	as palavras aceitas pelo autômato $M$ ou geradas pela gramática $G$	$L(G)=L(M)$
$2^{{\Sigma }^{\ast }}$		o conjunto de todas as linguagens sobre $\Sigma$
$a^n=\underset{n}{\underbrace{aa\dots a}}$	chave por baixo	indica quantas vezes algo se repete
$⟨nome⟩$	”nome” entre sinais	um lugar a preencher (uma categoria, não um texto literal), como nas gramáticas de linguagens de programação	$⟨valor⟩$
aa, $\text{for}$	fonte de código	palavra literal, exatamente como está escrita	abba

5. Gramáticas

Símbolo	Lê-se	Significado	Exemplo
$G=(V_n,V_t,S,P)$		gramática nos slides: não terminais, terminais, símbolo inicial, produções
$G=(V,T,P,S)$		a mesma coisa no Menezes ($V$ = variáveis, $T$ = terminais)
$A,B,S$ (maiúsculas)	não terminal	símbolo que ainda vai ser substituído	$S$ é o inicial
$a,b,0,1$ (minúsculas e dígitos)	terminal	símbolo que aparece na palavra final
$A\to aB$	$A$ produz $aB$	produção (regra de reescrita)	$S\to aS$
$A\to aB\mid b$	$A$ produz $aB$ ou $b$	a barra junta várias produções do mesmo lado esquerdo	$S\to aS\mid \epsilon$
$\alpha \Rightarrow \beta$	$\alpha$ deriva $\beta$	um passo de derivação: aplicar uma produção	$S\Rightarrow aS\Rightarrow aa$
${\Rightarrow }^{\ast }$	deriva em zero ou mais passos		$S{\Rightarrow }^{\ast }aab$
${\Rightarrow }^{+}$	deriva em um ou mais passos
$S^{\prime }$	$S$ linha	um novo símbolo inicial, criado para poder acrescentar $S^{\prime }\to \epsilon$
$A\to \epsilon$	$A$ produz vazio	$A$ pode sumir	$X\to \epsilon$ marca $X$ como final na conversão AF para GR

6. Expressões regulares

Símbolo	Lê-se	Significado	Exemplo
$\alpha \mid \beta$ (slides) ou $\alpha +\beta$ (Menezes)	$\alpha$ ou $\beta$	união	$a\mid b$ gera $a$ e $b$
$\alpha \beta$	$\alpha$ seguido de $\beta$	concatenação	$ab$
${\alpha }^{\ast }$	$\alpha$ estrela	zero ou mais repetições	$a^{\ast }$: $\epsilon ,a,aa,\dots$
${\alpha }^{+}$	$\alpha$ mais	uma ou mais repetições, igual a $\alpha {\alpha }^{\ast }$	$a^{+}$: $a,aa,\dots$
${\alpha }^{?}$	$\alpha$ opcional	zero ou uma vez, igual a $\alpha \mid \epsilon$	${-}^{?}{D}^{+}$: número com sinal opcional
$()$	parênteses	agrupam, como na álgebra	$(ab{)}^{\ast }$ é diferente de $a{b}^{\ast }$
$\varnothing$, $\epsilon$		também são expressões regulares: a linguagem vazia e a linguagem $\{\epsilon \}$

Precedência (quem “gruda” primeiro): repetição (${}^{\ast }$, ${}^{+}$, ${}^{?}$) > concatenação > união. Então $a{b}^{\ast }\mid c$ é $(a(b^{\ast }))\mid c$.

7. Autômatos

Símbolo	Lê-se	Significado	Exemplo
$M=(K,V,T,i,F)$		autômato nos slides: estados, alfabeto, transição, inicial, finais
$M=(\Sigma ,Q,\delta ,q_0,F)$		o mesmo no Menezes (o Ramos usa a ordem $(Q,\Sigma ,\delta ,q_0,F)$)
$K$ ou $Q$		conjunto de estados
$F$		conjunto de estados finais (de aceitação)	$F=\{q_2\}$
$q_0$ ou $i$	q zero	estado inicial
$q_f$, $Z$	q f, Z	nome usual para um estado final, principalmente o novo final criado na conversão GR para AF
$T(q,a)=p$ ou $\delta (q,a)=p$		do estado $q$, lendo $a$, vai para $p$	$T(q_0,a)=q_1$
$T:K\times V\to K$		assinatura do AFD: um estado de destino
$T:K\times V\to 2^K$		assinatura do AFND: um conjunto de destinos	$T(q_0,a)=\{q_0,q_1\}$
$\delta :Q\times (\Sigma \cup \{\epsilon \})\to 2^Q$		assinatura do AF com transições vazias
$\hat{T}$, $\hat{\delta }$ (às vezes $\check{T}$)	T chapéu	transição estendida, para uma palavra inteira	$\hat{T}(q_0,abab)=q_0$
$q\stackrel{a}{\to }p$	$q$ vai para $p$ com $a$	seta rotulada, forma curta de $T(q,a)=p$	$q_0\stackrel{0}{\to }{q}_1$
$\stackrel{\mathrm{0..9}}{\to }$		rótulo que vale para cada símbolo do intervalo	dígitos
$(q,w)$	configuração	”estou no estado $q$ e ainda falta ler $w$“	$(q_0,abab)$
$⊢$	produz em um passo	um passo de computação (Ramos)	$(q,ay)⊢(p,y)$
${⊢}^{\ast }$	produz em zero ou mais passos	a computação inteira	$(q_0,w){⊢}^{\ast }(q_f,\epsilon )$
$K^{\prime }$, $T^{\prime }$, $F^{\prime }$, $M^{\prime }$	K linha etc.	as partes do novo autômato construído a partir de outro	o AFD $M^{\prime }$ vindo do AFND $M$
$[q_0,q_1]$		um único estado do AFD que representa o conjunto $\{q_0,q_1\}$ do AFND	construção de subconjuntos
$\to$ na tabela		marca a linha do estado inicial	$\to q_0$
$\ast$ na tabela		marca a linha de um estado final	$\ast q_2$
${\times }_1$, ${\times }_2$, $\equiv$		na tabela de minimização: par marcado no passo 2, par marcado no passo 3, par equivalente	08 - Tópicos Complementares dos Livros
lido / escrito		rótulo de transição da máquina de Mealy: símbolo lido e saída

Como ler os diagramas

Desenho	Significado
círculo	um estado
círculo duplo	estado final
seta que não sai de nenhum estado	aponta para o estado inicial
seta de um estado para outro com rótulo a	transição lendo a
rótulo a,b	a mesma seta vale para a e para b
seta que volta para o próprio estado (laço)	lendo aquele símbolo, fica onde está
seta com $\epsilon$	transição vazia: muda de estado sem ler nada
estado sem saída e não final	estado poço: entrou, rejeita

8. Separadores e marcações do texto

Estes não são notação matemática, só formatação das notas.

Símbolo	Onde aparece	Significado
·	títulos e listas curtas	só um separador visual, como uma vírgula
→ (no meio do texto)	flashcards e explicações	”vai para” ou “vira”. Em $q_0\to q_1\to q_3$ é a sequência de estados visitados; em $A\to aB$ é uma produção
↔	tabelas	”corresponde a” (estado ↔ não terminal)
≡ entre siglas	mapa	”é equivalente a” (AFD ≡ AFND: reconhecem as mesmas linguagens)
${}^1,{}^2,{}_1,{}_2$	fórmulas	índices e expoentes comuns: $L_1$ é “a primeira linguagem”, $B_5$ é “o quinto número de Bell”

9. Símbolos do Obsidian

O que você vê no arquivo	O que é
$ ... $ e $$ ... $$	fórmula em LaTeX: dentro da linha e em destaque
[[Nome da nota]]	link para outra nota
[[Nota|texto]]	link que mostra outro texto
![[assets/figura.svg|320]]	imagem embutida, com 320 pixels de largura
> [!tipo] Título	callout (caixa colorida). O - depois do tipo deixa a caixa fechada até você clicar
**texto**	negrito
`texto`	fonte de código, usada aqui para palavras literais como abba
- [ ]	item de checklist (clique para marcar)
--- no topo	propriedades da nota (tags, apelidos)
a tag de flashcards e os separadores :: e ?	formato do plugin Spaced Repetition, veja Flashcards

10. Símbolos com mais de um significado

É aqui que mais se erra na prova, porque o mesmo desenho muda de sentido conforme o assunto.

Símbolo	Sentido 1	Sentido 2	Sentido 3
$\mid$	”tal que”, dentro de $\{x\mid \dots \}$	“ou”, entre produções: $S\to a\mid b$	união em ER: $a\mid b$
$+$	uma ou mais vezes: ${\Sigma }^{+}$, $a^{+}$	união em ER no Menezes: $a+b$	soma comum
$\ast$	zero ou mais: ${\Sigma }^{\ast }$, $a^{\ast }$	fecho de uma relação: $R^{\ast }$, ${⊢}^{\ast }$, ${\Rightarrow }^{\ast }$	estado final na tabela de transição
$\to$	função: $f:A\to B$	produção: $A\to aB$	estado inicial na tabela; sequência de estados
$\Rightarrow$	implicação lógica (aula 02)	passo de derivação (gramáticas)
$\equiv$	congruência módulo $n$	estados equivalentes na minimização	formalismos que reconhecem as mesmas linguagens
$\times$	produto cartesiano $K\times V$	multiplicação	par marcado (${\times }_1$) na minimização
$2^{\dots }$	potência de 2: $2^n$ estados	conjunto das partes: $2^K$
$||$	tamanho de palavra: $|w|$	número de elementos: $|A|$	valor absoluto: $|2a|$
$\epsilon$	a palavra vazia	rótulo de transição vazia

Treino: traduza as fórmulas para o português

1. $L=\{w\in \{a,b{\}}^{\ast }\mid |w|\text{ eˊ par}\}$

“L é o conjunto das palavras $w$ formadas por a e b (incluindo a vazia) tais que o tamanho de $w$ é par.”

2. $T:K\times V\to 2^K$

“T recebe um estado e um símbolo e devolve um conjunto de estados.” É a assinatura de um AFND.

3. $S{\Rightarrow }^{\ast }w$

“A partir do símbolo inicial $S$, aplicando zero ou mais produções, chega-se à palavra $w$.” Quer dizer que $w\in L(G)$ se $w$ só tem terminais.

4. $(q_0,w){⊢}^{\ast }(q_f,\epsilon )$ com $q_f\in F$

“Começando em $q_0$ com a palavra $w$ inteira para ler, depois de alguns passos o autômato chega a um estado final sem nada para ler.” Ou seja, $w$ é aceita.

5. $\hat{\delta }(q_0,w)\cap F\ne \varnothing$

“O conjunto de estados em que o AFND pode terminar depois de ler $w$ tem pelo menos um estado final.” É a condição de aceitação do AFND.

6. $(a\mid b{)}^{\ast }abb$

“Qualquer sequência de a e b (inclusive nenhuma) seguida de abb.” São as palavras terminadas em abb.

7. Se $\epsilon \notin L$, então $L^{+}=L^{\ast }-\{\epsilon \}$

“Se a palavra vazia não está em $L$, o fecho positivo de $L$ é o fecho de Kleene sem a palavra vazia.” Se $\epsilon \in L$, os dois fechos são iguais.