Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In the context of this statement, what does 'a & b are terminals' mean?

Stacks and queues can be used for determining whether a particular input string is in the language or not.

L = {a^nb^m | m,n >= 0, m >= n, and a & b are terminals}

Sample strings in L : abb, aabb, aabbb

Sample strings NOT in L : aab, ba

share|cite|improve this question
Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – FrankW Aug 5 '14 at 4:29
Have you googled? Even Wikipedia has the answer. – Raphael Aug 5 '14 at 8:05
@Raphael Yes I googled. 'Terminal characters', 'terminal Strings', 'Terminal numbers', 'terminals'. While it might be buried in one of those searches somewhere, it was not apparent or at the top of the list. Of course everything can be found on some other site somewhere if you already knew what to search for. One of the purposes of Stack Exchange is making information easier to find, IMO. – Steve M Aug 5 '14 at 15:30
Na, that's certainly not a purpose. It happens incidentally. That said, all of your search terms are "programmer style"; I see why it's hard to find CS information that way (and it's not your fault). Googling for "terminal symbol" immediately leads to the correct information. Teaching people the "right" words, now that's a purpose for the site! :) – Raphael Aug 5 '14 at 20:42
up vote 6 down vote accepted

It means that $a$ and $b$ cannot be further decomposed. For example we might consider the language $$ L_1=\{r^ns^m\mid n, m \ge 0, m\ge n, r\text{ and }s \text{ are 2-character strings over } \{a, b\}\} $$ In this language, $r$ and $s$ could be any of $aa, ab, ba, bb$, so a string in $L_1$ could be $bababbbbbb$, since with $r=ba, s=bb$ we could write it as $(ba)^2(bb)^3$. In effect, saying "$a$ is terminal" asserts that it's a character in the underlying alphabet.

The original definition of $L$ is reasonable, but rarely used in my experience. An equivalent statement would be $$ L=\{w\in \{a, b\}^*\mid w=a^nb^m, n, m\ge 0, m\ge n\} $$ or the alphabet $\{a, b\}$ would be inferred from context and usually wouldn't be stated. On any of my students' work, I'd accept $$ L=\{a^nb^m\mid n, m\ge 0,m\ge n\} $$

share|cite|improve this answer
You are too polite regarding the original definition of $L$. Writing $a$ and $b$ this way they become "variables", like $m,n$ are integer variables in this context. – Hendrik Jan Aug 5 '14 at 11:11
@HendrikJan. You're right; I misread the OP. I'm still not happy with the original, but I can't come up with a better was of rephrasing it. – Rick Decker Aug 19 '14 at 15:50
Your formulation is OK of course! – Hendrik Jan Aug 20 '14 at 23:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.