CODEWITHSUNDEEP
automata
Sherry W. Birkin
Sherry W. Birkin

Reputation: 11

Pushdown Automata definition

I am quite confused about formal description of PDA (push down automata)

If we write down L(M), this means that PDA M recognizes language L, correct ?

then , L(M)* means that PDA M recognizes that L* right ?

but what is the L* means ? how PDA can recognize infinite combination of L ?

Upvotes: 0

Views: 304

Answers (1)

Victor Stafusa
Victor Stafusa

Reputation: 14613

L(M)* means that PDA M recognizes that L* right ?

No! It means a language which is constituted from the concatenation of any number of sentences (including zero) that are valid in the language recognized by the PDA M.

Given that L(M) is context-free, it is easy to prove that L(M)* is context-free too.

To construct L(M)* , just take all the grammar of L(M), take the starting symbol S from L(M) and add two new productions R -> S R and R -> empty where R is the starting symbol of L(M)*.

So, given that L(M)* is context-free, then there is some PDA that recognize it. If you could construct a PDA for L(M), then a PDA for L(M)* should be trivial to construct, given that it is almost the same as L(M) just with two extra productions.

Upvotes: 2

Related Questions