[Solved]: What could 'two characters are terminals' mean?

Problem Detail: 

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

Asked By : Steve M

Answered By : Rick Decker

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\} $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28926

3.2K people like this

 Download Related Notes/Documents