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

Topic revision: r1 - 2013-02-11 - BarrinG

 Home H401 Web View Edit Account
Copyright © 2008-2019 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