Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with proof-techniques
Search options not deleted
user 65888
Questions about general methods and techniques for proving multiple theorems. When asking about the proof of a single statement, use tags relating to what the proof is about instead.
1
vote
1
answer
10k
views
Pumping Lemma: 1^n^2 is not regular
I am attempting to prove via the pumping lemma that $1^{n^2}$ is not a regular language. I started with
$w = 1^{p^2}$
I then divided $w$ into $xyz$, where:
$x = 1^{l}$
$y = 1^{m}$
$z = 1^{{p^2}- …
- 375
1
vote
1
answer
300
views
Is $A_{PTM}$ a BPP-complete language?
The language $A_{PTM}$ is defined as the acceptance problem on a Probabilistic Turing machine.
$A_{PTM}=$ { $<M, x> | M$ on input $x$ accepts with an error probability less than or equal to 1/3}
Ba …
- 375
4
votes
1
answer
2k
views
Every LEFT-RESET Turing machine has an equivalent conventional Turing machine
I am working on a proof of the theorem that every LEFT-RESET Turing machine has an equivalent conventional, single tape Turing machine. The transitions for the LEFT-RESET Turing machine are {Right, RE …
- 375
0
votes
0
answers
408
views
Writing a constructive proof for closure of a regular language under homomorphism
I've spend the last few days searching online for an example of a constructive proof of regular languages being closed under homomorphism, but I have not seen one. I am mostly unsure of how to show th …
- 375
2
votes
2
answers
690
views
Prove L = {a = b ⊕ c | a, b, c ∈{0, 1}*} is not regular
Given that language $L = \{a = b ⊕ c \mid a, b, c ∈ \{0,1\}^*, a = b \oplus c\}$, with an alphabet $Σ = \{⊕, =, 0, 1\}$, I need to prove that this language is not regular. The following is as far as I …
- 375
0
votes
1
answer
95
views
Prove a language $A_{PTM}$ is not BPP-Complete
I am trying to prove that there are a language is not BPP-Complete. There are a couple of examples online, but they are not the best examples and are a bit complicated. I spoke with one of my computer …
- 375
2
votes
2
answers
2k
views
Proof Idea: How to prove the intersection of regular language and CFL is a CFL?
I know that the intersection of a regular language and a context free language is a context free language. I've seen this fact proven on here and other websites. However, after spending hours reading …
- 375