All Questions
9 questions
0
votes
0
answers
41
views
Complement of a language definition
Let $A=\{$ M is a TM, $s\in \mathbb{N}$ and $\exists x\in\Sigma^*$ s.t M rejects $x$ in at most $s$ steps $\}$.
I want to define its complement, so how do I negate "$\exists x\in\Sigma^*$ s.t M ...
- 47
1
vote
1
answer
207
views
Finite languages $L\in RE$
I want to check if I understood it in the right way.
In some example where $L\in RE$ the explanation deal with 2 cases: 1st when $L$ finite and 2nd when $L$ infinite. In the second case $L\in R$, isn'...
- 373
1
vote
1
answer
93
views
Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular
Prove that $L = \{ xy \in \{a,b\}^* \mid |x|_a = 2|y|_b
\}$ is not regular.
I have already tried to prove it by using the pumping lemma and reduction to absurdity, but have been unsuccesful on both. ...
- 11
1
vote
1
answer
119
views
Is Language $ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $ context free?
$ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $
I would use the Ogden pumping lemma. Assumption $n < m$ where $n$ is a number from lemma. My ...
- 53
2
votes
2
answers
446
views
Recursive definition of a language $ L $ over $ \{a,b\} $
How would I start the recursive definition of the following language:
L over {a, b} such that L consists of strings in which each
occurrence of b is immediately preceded and followed by an a
The '...
2
votes
1
answer
435
views
Is computing the cardinality of sum of regular expressions without kleene star closure EXPTIME problem?
Is computing the cardinality of sum of regular expressions without kleene star closure is EXPTIME problem?
Note that sum of regular expressions is union of regular expressions. The alphabet of each ...
0
votes
1
answer
252
views
Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars?
Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars, i.e. a word/string that can be derived from each regular grammar.
...
0
votes
0
answers
37
views
Proof that {w ∈ {a, b} ∗ | |w|a = |w|b} is not a regular language [duplicate]
I know that the language {w ∈ {a, b}∗| |w|a = |w|b} is not regular since somehow, you can't store all the information needed in a DFA. I've seen that normally it's done with reduction to absurdity or ...
- 1
6
votes
2
answers
121
views
What is the field studying the search and generation of computer programs?
This Github repo hosts a very cool project where the creator is able to, give an integer sequence, predict the most likely next values by searching the smallest/simplest programs that output that ...
- 441