# Questions tagged [notation]

Use this tag whenever you have a question about what some particular symbol/notation means.

193 questions
Filter by
Sorted by
Tagged with
33 views

### An elementary question about grammar

Recently, I am studying grammar in automata. And, I have few information about this subject. I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$. Is it true if I say that $S\to aASA$ ...
88 views

### Understanding reductions and notation

I am currently working through Sipser's Introduction to the Theory of Computation. In chapter 5, he defines that a Language $A$ is mapping reducible to language $B$, written $A\leq_m B$ if there is a ...
57 views

### Is there a common notation for describing this operation $coNP\; ? \; NP = DP$?

While working with complexity classes, I've come along the definition of $DP$ (or $D^p$): $$DP = \{L_1 \cap L_2 \mid L_1 \in NP \text{ and } L_2 \in coNP\}$$ I am interested in a different (and much ...
65 views

### Function types in Computer Science Metanotation

See Guy Steele's slides for what I refer to by "Computer Science Metanotation", specifically the bits about BNF. I often make use of the BNF syntax observed there, as a substitute for ...
40 views

### When to use subscript and when to make it a function?

Let's say, I have a set of cats $C = \{ a, b, c, ... \}$. Each cat has a tail. I can say, that the lengths of the tails of cats are denoted as $t_a$, $t_b$, etc. Otherwise, I can say that they are ...
3k views

644 views

### Same notation/terminology for union of sets and concatenation (Kleene star)?

For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology ...
1 vote