5 votes 5 votes Which of these languages are deterministic? $L_{1} =$ $\left \{a^{n}b^{n}: n \geq 1 \right \}\cup \left \{ b \right \}$ $L_{2} =$ $\left \{a^{n}b^{n}: n \geq 1 \right \}\cup \left \{ a \right \}$ Theory of Computation context-free-language theory-of-computation + – Mk Utkarsh asked Mar 28, 2018 Mk Utkarsh 781 views answer comment Share Follow See 1 comment See all 1 1 comment reply Mk Utkarsh commented Mar 29, 2018 reply Follow Share Deterministic context-free languages are closed under union with regular languages. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes L1--->DCFL L2---->NCFL abhishekmehta4u answered Mar 28, 2018 abhishekmehta4u comment Share Follow See all 14 Comments See all 14 14 Comments reply Show 11 previous comments srestha commented Mar 28, 2018 reply Follow Share @Utkarsh chk is not ur grammar accpting aaabb too? I mean there should be a transition from $q_{3}$ to $q_{4}$ but not any transition from $q_{3}$ to $q_{2}$ right? then an extra a is there in grammar 0 votes 0 votes Mk Utkarsh commented Mar 28, 2018 reply Follow Share when we finished reading $aaa$ from $aaabb$ we have stack $111z$ reading next b stack became $11z$ again reading next b stack is $1z$ now we need one more b otherwise DPDA won't accept 0 votes 0 votes Mk Utkarsh commented Mar 28, 2018 reply Follow Share and it is accepting $ab$ and also $a$ whether transition is from $q_{3}$ to $q_{2}$ or from $q_{3}$ to $q_{4}$ DPDA's working is not affected 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Both L1 and L2 are deterministic CFL rish1602 answered Aug 20, 2021 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.