Which of the following languages are regular, context-free but not reg- ular, or non-context-free? Assume fixed...

 

Transcribed Image Text:

Which of the following languages are regular, context-free but not reg- ular, or non-context-free? Assume fixed alphabets Σ and N of >1 elements. (Here a brief explanation is sufficient.) (a) L₁= {ewewewzee € Σ, w₁, W2, W3 €. |w₁|=|w₂|}. (b) L₂= {ewewewe | e Σ, w₁, W2, W3 € *, |w₁| = |w₂|}. (c) L3= {ew₁w₂w3e | eΣ, w₁, W2, W3 € *, |w1| > |w2| = |w3|}. (d) L₁ = {ewewewzee e Σ, w₁, W2, W3 ED, w₁| < |w₂| ≤6}. (e) L5 = {ewewewzee , w, w3 € Σ* }. (f) L6 C (EU {e, o, (,), +,*})* is the set of regular expressions over Hints: Remember that we study here regular expressions them- selves, not the regular languages they define. Consider regular expressions without abbreviations (skipped parentheses). (g) L7 C (CUNU{})* is the set of productions of all the context- free grammars with the terminal alphabet Σ and the nonterminal alphabet N. Which of the following languages are regular, context-free but not reg- ular, or non-context-free? Assume fixed alphabets Σ and N of >1 elements. (Here a brief explanation is sufficient.) (a) L₁= {ewewewzee € Σ, w₁, W2, W3 €. |w₁|=|w₂|}. (b) L₂= {ewewewe | e Σ, w₁, W2, W3 € *, |w₁| = |w₂|}. (c) L3= {ew₁w₂w3e | eΣ, w₁, W2, W3 € *, |w1| > |w2| = |w3|}. (d) L₁ = {ewewewzee e Σ, w₁, W2, W3 ED, w₁| < |w₂| ≤6}. (e) L5 = {ewewewzee , w, w3 € Σ* }. (f) L6 C (EU {e, o, (,), +,*})* is the set of regular expressions over Hints: Remember that we study here regular expressions them- selves, not the regular languages they define. Consider regular expressions without abbreviations (skipped parentheses). (g) L7 C (CUNU{})* is the set of productions of all the context- free grammars with the terminal alphabet Σ and the nonterminal alphabet N.

Answer rating: 100% (QA)

a This language is regular A DFA for it would have 4 states to remember 0w mod 2 and 1w mod 2 A DFA ... View the full answer