What is Parikh Theorem in theory of computation?

In the theory of computation, the Parikh theorem elaborates something more about Context-Free Languages. According to this theorem for any context-free language L, if we observe only the relative number of occurrences of terminal symbols of strings in language L irrespective of their order, then A is trivial(null) from a regular set.

Formally, let Σ= {a1.......... ak}. The Parikh map is a function 

is defined by  -

​​​​​​​That is, ψ(x) records the number of occurrences of each symbol in x. The structure Σ* with binary operation (·) (concatenation) and constant E forms a monoid, as does the structure N^k with binary operation (+) component-wise addition) and identity = (0, ... , 0), and ψ is a monoid homomorphism:

                                                    ψ(x,y)= ψ(x)+ ψ(y),

The major thing you find between the monoids Σ* and N^k is that among two N^k is commutative, whereas Σ*  is not, except in the case k = 1. In fact, if ≡ is the smallest monoid congruence on Σ* such that a_i, a_j, ≡a_j a_i, , 1 ≤ i, j ≤ k, then N_k is isomorphic to the quotient Σ*/≡ .  The monoid Σ* is sometimes called the free monoid on k generators, and N^k is sometimes called the free commutative monoid on k generators. The word "free" refers to the fact that the structures do not satisfy any equations besides the logical consequences of the monoid or commutative monoid axioms, respectively.

Theorem: (Parikh) For any context-free language A, ψ(A) is semilinear.
The converse does not hold: the set {aⁿbⁿcⁿ | n ≥ 0} is not context-free but has a semilinear image under ψ. This is also an image of the CFL {(ab)ⁿcⁿ | n ≥ 0 } and the regular set (abc)*.

 Also, Study about: 

• Mealy Machine
• Moore Machine
• Rice Theorem
• Brief about Turing Machine
• Multi Dimension Turing Machine
• Multiple Turing Machine
• Parikh Theorem in TOC
• Parse Tree or Derivation Tree
• What do you Understand by Derivation
• MyHill Nerode Theorem
• Minimize Myhill Nerode Theorem
• Push Down Automata
• Know Where we use Automata
• What do you understand by Derivation of Grammar
• What is Context-free Grammar
• Example based on CFG
• Regular Expression in TOC
• What is Two-way infinite Turing machine?
• Example to generate Parse tree from the given grammar

Also Read, some interview tips

• Why Should I Hire You?
• What are your weaknesses?
• What are your greatest strengths?
• Tell me about yourself.
• What's the reason behind leaving your current position at your company?
• Do You Know how the power of Keywords impacts on Resume?
• Top 8 Proofreading Tips and Techniques in 2022.
• Top Ten Technical Resume Writing Tips in 2022.
• Tips for your resume before you get entry to Job Market
• What Questions you can ask HR during the Interview.
• How to make an impressive resume?
• Best Resume writing Technique.
• What Questions you can ask HR during the Interview.