Question

For Automata class:

Let L be a regular language over the binary alphabet. Consider the following language over the same alphabet: L' = {w | |w| = |u| for some u ∈ L}. Prove that L' is regular.

Answer #1

**Your** **Explanation** :

------------------------

L is regular, there is a DFA D that accepts the language L

For each transition in DFA having

A -> B on symbol x

Change it to have each and every symbol in the alphabet

```
For example if A -> B is on 0
Alphabet is {0, 1}
Make it like
A -> B on 0
A -> B on 1
```

This way we have an NFA now which accepts the language L0.

So, L0 is regular.

------------------------------------------------------------------------------------------------------------

**Note** : Please thankful the answer, if you like
it, as it would be of great help to me..!!

------------------------------------------------------------------------------------------------------------

5 A Non-Regular language
Prove that the language}L={www∣w∈{0,1}∗} is not regular.

Consider the language L3 over alphabet Σ = { a, b }, L3 = { w ∈
Σ* | w is a palindrome of any length}.
Construct a PDA that recognizes L3.
Implement that PDA in JFLAP

Let Σ = {a}, and let L be the language
L={an :nisamultipleof3butnisNOTamultipleof5}.
Is L a regular language? HINT: Maybe instead of an explicit DFA
or regular expression, you can find another argument.

Let L ⊆ Σ* be a regular language. Suppose a ∈ Σ and
define L\a = {x : ax ∈ L }. Show that L\a is regular.

Are the following languages over {a, b} regular? If they are
then prove it. If they are not prove it with the Pumping Lemma
{an bm | m != n, n >= 0}
{w | w contains the substring ‘aaa’ once and only once }
Clear concise details please, if the language is regular,
provide a DFA/NFA along with the regular expression. Thank you.
Will +1

The chopleft
operation of a regular language L is removing the leftmost symbol
of every string in L:
chopleft(L) = { w | vw
∈ L, with |v| = 1}.
Prove or disprove that
the family of regular languages is closed under the
chopleft operation.
Hint: If it’s regular,
give an idea of constructing an FA that accepts chopleft(L) using
an FA M that accepts L.
Otherwise, give a
counterexample.

Find a regular expression to describe:
The set of all strings over the alphabet {a, b, c, d}
that contain exactly one a and exactly one b
So, for example, the following strings are in this
language:
ab, ba, cccbad, acbd, cabddddd, ddbdddacccc
and the following strings are NOT in this
language:
a, ccbc, acbcaaacba, acacac, bcbbbbbca, aca, c, d,
b

Consider the language defined by L =
{aibmcn | i > 0, n > m >
0 }
Is L regular or not? Prove it

Consider the language L = { w w : w ∈ { 0 , 1 } ∗ } is not
context-free. Note that this is the language of all strings that
consist of some combination of 0s and 1s, followed immediately by
that same combination of 0s and 1s. For example, 0101, 101101, and
110110 are all in the language because they consist of a string
followed by itself. Can you build a PDA to recognize this language?
(Hint: you...

Please answer True or False on the following:
1. Let L be a set of strings over the alphabet Σ = { a, b }. If
L is infinite, then L* must be infinite (L* is the Kleene closure
of L)
2. Let L be a set of strings over the alphabet Σ = { a, b }. Let
! L denote the complement of L. If L is finite, then ! L must be
infinite.
3. Let L be...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 12 minutes ago

asked 36 minutes ago

asked 45 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago