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

Expert Solution

The language is not regular. The proof using Pumping Lemma for the same has been upload as image downside. Pumping lemma is used as a proof for irregularity of a language. If a language is regular, it must always satisfies pumping lemma.

If you find any diificulty understanding the text or if you find the answer is incorrect, please let me know in the comment section.

Here goes the answer.....

Hope this helps you... Give it a thumps up...

venereology answered 1 year ago

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 = { aib2i : i > 0} 2) Prove the language M is not regular, over the alphabet Σ = {a, b}. M = { wwR : w is an element of Σ* i.e. w is any string, and wR means the string w written in reverse}. In other words, language M is even-length palindromes.

Show that the language ?={?^??^??^?:?≥0,?≥0}is not 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 whether or not the following languages are regular. If the language is regular then give...

Determine whether or not the following languages are regular. If the language is regular then give an NFA or regular expression for the language. Otherwise, use the pumping lemma for regular languages or closure properties to prove the language is not regular. 1) L = { 0 n1 k : k ≤ n ≤ 2k} 2) L = { 0 n1 k : n > 0, k > 0 } È { 1 k0 n : k > 0, n...

Given a regular language A, define L2 = { xz | there exists y Σ*, xyz...

Given a regular language A, define L2 = { xz | there exists y Σ*, xyz A, |x|=|z|, |y| = 2 }. Decide with a formal proof if L2 is (a) regular; or (b) not regular but context-free; or (c) not context-free.

Question 4 Prove that the following language is not regular. ? = { 0 ?1 ?...

Question 4 Prove that the following language is not regular. ? = { 0 ?1 ? | ?, ? ≥ 0, ? ≠ 2? + 1 } Question 5 Prove that the following language is not regular. ? = { ? ∈ { 0, 1, 2} ∗ | #0 (?) + #1 (?) = #2 (?) } where #? (?) denotes the number of occurrences of symbol a in string w.

Write regular expressions that describes the following language: The language over {0,1,/} that contains all and...

Write regular expressions that describes the following language: The language over {0,1,/} that contains all and only the strings that are base-2 (as above, you can use base-10 if you prefer) representations of rational numbers. Define a representation of a rational number to be either a representation of an integer, or two representations of integers separated by “/”. Leading 0s are allowed this time.

Write regular expressions that describes the following language: The language over {0,1} that contains all and...

Write regular expressions that describes the following language: The language over {0,1} that contains all and only the strings that are base-2 representations of odd positive integers. Do not allow leading 0s. (If you are more comfortable writing bulky regular expressions than you are working in base-2, you may write a regular expression for strings that are base-10 representations of odd integers without leading 0s, using alphabet {0,1,2,3,4,5,6,7,8,9}.)

The following language over Σ = {1, #} contains #-separated lists of distinct unary values: A...

The following language over Σ = {1, #} contains #-separated lists of distinct unary values: A = {x1#x2# . . . #xk | k ≥ 0, xi = 1∗ for all i = 1 . . . k, xi 6= xj for all i 6= j} Use the pumping lemma to show A is not regular. In other words, give a string s ∈ A and argue that no matter how you partition s = xyz with |y| > 0,...

Write a regular expression for the language of all strings over {a,b} in which every b...

Write a regular expression for the language of all strings over {a,b} in which every b is directly preceded by a, and may not be directly followed by more than two consecutive a symbols.

Question