Question II: Consider the language L below. If L is a regular language, construct the corresponding...

Question II:

Consider the language L below. If L is a regular language, construct the corresponding DFA. If not, prove that L is not a regular language.

L= {0n10n | n ≥1}

Consider the language M consisting of those strings of 0’s and 1’s that have an equal number of 0’s and 1’s (not in any particular order). Suppose we know M is not a regular language. Consider the language N consisting of those strings of 0’s and 1’s that have an unequal number of 0’s and 1’s. Either construct a finite automaton A such that L(A) = N, or prove N is NOT a regular language.

Expert Solution

Any queries please comment

Please thumbsup for my effort

Thank you and all the best

venereology answered 1 year ago

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

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.

Consider the ternary number system. What is the corresponding regular expression of a DFA that accepts...

Consider the ternary number system. What is the corresponding regular expression of a DFA that accepts ternary strings that are not divisible by nine?

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.

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

Consider the language defined as such: L = { w$w’ : w is a string of...

Consider the language defined as such: L = { w$w’ : w is a string of numbers 0-9 and can be of length ≥ 0, and w’ is the reverse string of w} Write a recursive grammar that defines all strings in the language. Using the language above, write the Java code (using recursion) that will recognize if a string is part of the language or not.

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...

Show that the language ?={?^??^??^?:?≥0,?≥0}is not regular.

In C++ Consider the language L = { s$s' : s is a possibly empty string...

In C++ Consider the language L = { s$s' : s is a possibly empty string of characters other than $ , s' = reverse( s )} as defi ned in Chapter 6 . Write a recognition algorithm for this language that uses both a queue and a stack. Thus, as you traverse the input string, you insert each character of s into a queue and each character of s' into a stack. Assume that each input string contains exactly...

Consider the language L over alphabets (a, b) that produces strings of the form aa* (a...

Consider the language L over alphabets (a, b) that produces strings of the form aa* (a + b) b*a. a) Construct a nondeterministic finite automata (NFA) for the language L given above. b) Construct a deterministic finite automaton (DFA) for the NFA you have constructed above.

Question