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.

Solutions

Expert Solution

Any queries please comment

Please thumbsup for my effort

Thank you and all the best

venereology answered 2 months ago

Next > < Previous

Related Solutions

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.

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

Regular => Context-Free Give a proof by induction on regular expressions that: For any language A,...

Regular => Context-Free Give a proof by induction on regular expressions that: For any language A, if A is regular, then A is also context-free. You may assume that the statements from the previous Closure under Context-Free Languages problem are proved. R is a regular expression if RR is: a for some a∈alphabet Σ, the empty string ε, the empty set ∅, R1∪R2, sometimes written R1∣R2, where R1 and R2 are regular expressions, R1∘R2, sometimes written R1R2, where R1 and...

Consider the compounds with the generic formulas listed below and their corresponding molar solubilities in pure...

Consider the compounds with the generic formulas listed below and their corresponding molar solubilities in pure water. AX2 ;molarsolubility= 1.75×10−4 M A2X ;molarsolubility= 2.25×10−4 M AX ;molarsolubility= 1.25×10−6 M Part A Which compound will have the smallest value of Ksp? a. AX b. AX2 c. A2X

5 Regular => Context-Free Give a proof by induction on regular expressions that: For any language...

5 Regular => Context-Free Give a proof by induction on regular expressions that: For any language A, if A is regular, then A is also context-free. You may assume that the statements from the previous Closure under Context-Free Languages problem are proved.

Construct an NPDA that accepts the language defined by the given grammar and give the language...

Construct an NPDA that accepts the language defined by the given grammar and give the language in a formal expression (including a regular expression). S -> AA|a, A-> SA|ab

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

Subjects