1. Prove the language L is not regular, over the alphabet Σ = {a, b}. L...

1. Prove the language L is not regular, over the alphabet Σ = {a, b}. L = { aⁱb²ⁱ : i > 0}

2) Prove the language M is not regular, over the alphabet Σ = {a, b}. M = { ww^R : w is an element of Σ* i.e. w is any string, and w^R means the string w written in reverse}. In other words, language M is even-length palindromes.

Expert Solution

venereology answered 9 months ago

Given an alphabet Σ, what are the languages L over Σ for which L ∗ is...

Given an alphabet Σ, what are the languages L over Σ for which L ∗ is finite? How many such languages exist?

Is the following language a regular language? ( Prove with pumping Lenma ) L = {...

Is the following language a regular language? ( Prove with pumping Lenma ) L = { o^n 1^n 2^n | n => 0} Define CFL pumping lemma

Suppose A and B are regular language. Prove that AB is regular

Consider the language L1 over alphabet Σ = { 0, 1 } where the production rules...

Consider the language L1 over alphabet Σ = { 0, 1 } where the production rules for L1 are as follows: S → TT S → U T → 0T T → T0 T→ 1 U → 0U00 U → 1 Q → λ P → QU Transform this grammar into Chomsky Normal Form, consistent with the CNF specification in the Quick Reference, and using only Variables { S, T, U, V, W, X }. Implement that CNF grammar in...

Determine if the language ?={?^?∶?=?^3????????≥0}over Σ={?}is regular.

3. Are the following languages A and B over the alphabet Σ = {a, b, c,...

3. Are the following languages A and B over the alphabet Σ = {a, b, c, d} regular or nonregular? • For a language that is regular, give a regular expression that defines it. • For a nonregular language, using the pumping lemma prove that it is not regular. (a) A = {d 2j+1c k+1 | j ≥ k ≥ 0} · {c r+2b 2s+3 | r ≥ 0 and s ≥ 0} (b) B = {a 2j+2b k+3c j+1...

Automata Question. Over the alphabet Σ = {a, b}: 1) Give a DFA, M1, that accepts...

Automata Question. Over the alphabet Σ = {a, b}: 1) Give a DFA, M1, that accepts a Language L1 = { w | w has exactly 2 a’s } 2) Give a DFA, M2, that accepts a Language L2 = { w | w has at least 2 b’s } 3) Give acceptor for L1 intersection L2 4) Give acceptor for L1 - L2

Question