Register

Identify language

• edited by
4,347 views
11 11 votes
Consider the sets over $\left\{a,b\right\}$

$S_1=\left\{a,ab\right\};$

$S_2=\left\{b,ba\right\};$

$S_3=\left\{a^nb^{2n}\right\}\cup \left\{a^{2n}b^n\right\};$

$S_4=\left\{ww^R|w\in(a,b)^*\right\};$

$S_5=\left\{a^nb^nc^{2n}|n\geq1\right\};$

The number of sets in the above list that are accepted by a dfa by empty stack is ______________.

Explanation is given as S1, S2, S3 dont satisfy prefix property. But, why cant they be accepted by dfa (where we dont check prefix property satisfaction). If pda was given then they would have been right, I guess.

1 Answer

Best answer
14 14 votes

I do not know what is DFA with empty stack. So, assuming PDA with empty stack. 

S1 and S2 are finite languages and hence regular and hence CFL. S3 and S4 are CFLs. PDA with empty stack can accept the whole CFL without any exception and the language accepted by this and the PDA with acceptance by final state is one and the same. So, the answer should be 4 as only S5 is not a CFL. 

Now, consider PDA as DPDA. Now, the language accepted by a DPDA with empty stack is a proper subset of the language accepted by a DPDA with final state. This set (accepted by DPDA with empty stack) must obey the prefix property - if $w$ is in $L$, no prefix of $w$ must be in $L$, and is exactly the same as the language generated by a LR(0) grammar.

From the given sets the first 4 do not obey prefix property:

  1. $a$ prefix of $ab$
  2. $b$ prefix of $ba$
  3. $aab$ prefix of $aabbbb$ (not DCFL also)
  4. $a$ prefix of $aa$ (not DCFL also)

The last one is not even a CFL. So, none of these languages can be accepted by a DPDA with empty stack. A DPDA with final state can accept the first 2 sets but not the other two. 

• selected by
Voting & Accepting an answer helps improve the community
← Previous · Ace Test Series: Pro...Next → · Ace Test Series: Com...
← Previous in category · Regular expressionNext in category → · transition diagram f...
Position:
Show:

Related questions

1 1 vote
2 2 answers
2.8k
2.8k views
Shefali asked Oct 22, 2015
2,802 views
Identify language generated by CFG
Consider the following grammar,$S\rightarrow aSa|bSb|A$$A\rightarrow aBb$$B\rightarrow aB|bB|\epsilon$Identify the language generated by above CFGa. $L=\left\{ww^R \;|\; ...
1 1 vote
1 answers 1 answer
897
897 views
Utk asked Jan 4, 2016
897 views
Language and its compliment
Given $(L')^* = (L^*)' where ' is complement operation.$L$ is ?$ \phi, \{\epsilon \}$ and $ \Sigma^*$$\{\epsilon \}$ and $\Sigma^*$$ \phi $ and $\{\epsilon \} $$L$ is no...
1 1 vote
1 answers 1 answer
660
660 views
Shweta Singh Lodhi asked Oct 5, 2016
660 views
Language produced by CFG
Consider the context free grammar below. What language does it generates?S - 0B|1AA ->0|0S|1AAB ->1|1S|0BB