Parikh's Theorem is a result in formal language theory that will occupy us for much of the 2013 H401 seminar.

Let A be a nonempty alphabet with d letters. The Parikh map is a function from A* to N^d (where N

is the natural numbers) such that the i'th component of the vector P(w) is the number of occurrences

of the i'th letter of A in the string w. For example, with A = {a,b} and d = 2, P(ababbbba) = (3, 5).

The Parikh map is a monoid homomorphism from A* (under concatenation) to N^d (under vector addition).

If L is any language over A (a subset of A*), the Parikh image P(L) of L is the set {P(w): w in L}.

Parikh's Theorem can be stated in two ways:

1) The Parikh images of context-free languages are semilinear sets in N^d

2) If L is any context-free language, there exists a regular language R with P(L) = P(R)

-- BarrinG - 2013-02-11

Edit | Attach | Print version | History: r1 | Backlinks | Raw View | Raw edit | More topic actions

Copyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding UMass CS EdLab? Send feedback

Ideas, requests, problems regarding UMass CS EdLab? Send feedback