Theory of Computation problem: Proving that L = L(A)

In summary, the conversation is about a proof problem in the Theory of Computation. The problem involves proving that L = L(A) by showing that L ⊆ L(A) and L(A) ⊆ L. The relevant concepts and equations needed to solve the problem are mentioned, including mutual simple induction and the formal usage of transition function of DFAs. The asker of the question is unsure if the second part of the proof (L ⊆ L(A)) requires the first part (L(A) ⊆ L) to already be shown. More information is needed to fully understand the problem.
  • #1
s3a
818
8
Hello to everyone that's reading this. :)

1. Homework Statement

(Theory of Computation) proof problem about proving that L = L(A) by proving that L ⊆ L(A) and that L(A) ⊆ L:
https://www.docdroid.net/du7lLvh/theproblemanditssolution.pdf

Homework Equations


• Mutual simple induction
• Formal usage of transition function of DFAs (meaning knowing how to use the delta notation)
• Potentially, proof by contrapositive
• Knowing that A = B can be proven by proving A ⊆ B and B ⊆ A.

The Attempt at a Solution


My question is: does the "δ̂(p, w) = p ⇒ w has even number of 1's" from second part (L ⊆ L(A)) need the first part (L(A) ⊆ L) to already be shown, or is it completely independent, such that the second part (L ⊆ L(A)) could have been cut and pasted, verbatim, before the first part (L(A) ⊆ L)?

Any input would be GREATLY appreciated!
 
Physics news on Phys.org
  • #2
s3a said:
Hello to everyone that's reading this. :)

1. Homework Statement

(Theory of Computation) proof problem about proving that L = L(A) by proving that L ⊆ L(A) and that L(A) ⊆ L:
https://www.docdroid.net/du7lLvh/theproblemanditssolution.pdf

Homework Equations


• Mutual simple induction
• Formal usage of transition function of DFAs (meaning knowing how to use the delta notation)
• Potentially, proof by contrapositive
• Knowing that A = B can be proven by proving A ⊆ B and B ⊆ A.

The Attempt at a Solution


My question is: does the "δ̂(p, w) = p ⇒ w has even number of 1's" from second part (L ⊆ L(A)) need the first part (L(A) ⊆ L) to already be shown, or is it completely independent, such that the second part (L ⊆ L(A)) could have been cut and pasted, verbatim, before the first part (L(A) ⊆ L)?

Any input would be GREATLY appreciated!
Possibly the reason no one has replied is that there is not enough information here.
In the linked document it says
Let ##L = \{w \in \{0, 1\}* : \text{w has an odd number of 1's} \}##, and let A be the DFA with tabular representation ...
  1. Does the notation {0, 1}* mean an arbitrary sequence of 0's and 1's?
  2. What is a DFA? Presumably this acronym is unpacked in your textbook, but we don't have access to that information.
  3. What does the notation ##\hat \delta (p, w)## mean?
 

Related to Theory of Computation problem: Proving that L = L(A)

1. What is the Theory of Computation?

The Theory of Computation is a field of computer science that studies the nature and capabilities of computers, as well as the processes and algorithms used to solve problems.

2. What is the significance of proving that L = L(A)?

Proving that L = L(A) is important because it provides a way to determine if a language is decidable or not. This can help in understanding the limits of computation and can also have practical implications in fields such as cryptography and artificial intelligence.

3. What is the difference between L and L(A)?

L is the set of all languages that can be recognized by a Turing machine, while L(A) is the set of all languages that can be recognized by a specific automaton A. In other words, L(A) is a subset of L.

4. What are some techniques used to prove that L = L(A)?

Some common techniques used to prove that L = L(A) include constructing a finite state machine, using the Pumping Lemma, and using closure properties of regular languages.

5. Can L = L(A) be proved for all languages?

No, it is not possible to prove that L = L(A) for all languages. This is because there are languages that are not decidable, meaning there is no algorithm that can determine if a given string belongs to the language or not.

Similar threads

  • Calculus and Beyond Homework Help
Replies
13
Views
2K
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
951
  • Calculus and Beyond Homework Help
Replies
3
Views
963
  • Topology and Analysis
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
Back
Top