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
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Favorites infavorites:mine
infavorites:1234
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 Search options user 303

Questions related to formal languages, grammars, and automata theory

5
votes
You can choose the language of the halting problem $\qquad \displaystyle B_1 = \{\langle T \rangle \mid T \text{ halts on } \langle T \rangle\} \in B$ and its complement $\qquad \displaystyle C_1 = …
answered Jun 10 '12 by David Lewis
10
votes
Yes, $A$ is a CFL. Use the context free language (with the notation $|x|_0$ meaning what you have as #0's in $x$): $B=\{x\in \{0,1\}^*:3\cdot|x|_0=|x|_1\}$ and the morphism $f:\{a,b,c\}^*\rightarr …
answered Apr 28 '12 by David Lewis
2
votes
Hint... There may be a direct application of the pumping lemma, but I suggest you take a look at closure properties. Consider the non-CFL in the first answer to the reference post, $P=\{a^p:p \text{ …
answered May 14 '12 by David Lewis
3
votes
Below is a hint for working with the Turing Machine (TM) formalism for RE languages. But finishing that approach from the hint depends on how you've been working with TMs. You have a TM, say $T_L$ to …
answered May 8 '12 by David Lewis
8
votes
It is regular. Let's first work in binary, which will generalize to any base > 1. Let $M_{a,b}$ be the language in question. For a = 1, b = 0 we get $M_{1,0} = \{1, 10, 11, 100, 101, ...\}$ which …
answered Mar 22 '12 by David Lewis
4
votes
Hints... $L_a$ can be transformed into an well-known non-regular language by a very simple homomorphism that basically "loses" information. For $L_b$ you might try transforming it into its "opposite …
answered May 9 '12 by David Lewis
9
votes
Yes, $\mbox{Before}(\beta)$ and $\mbox{After}(\beta)$ are context-free languages. Here's how I would prove it. First, a lemma (which is the crux). If $L$ is CF then: $\mbox{Before}(L,\beta) = \{ …
answered Mar 26 '12 by David Lewis
6
votes
The first trick here is to think of the multiplication table as the transition table of an automaton $A$ with each state representing a letter in your multiplication table, but not worrying about acce …
answered Apr 24 '12 by David Lewis
28
votes
As Kaveh says in a comment, Kleene bestowed the name way back when he kicked off automata theory and formal languages. I believe the term was arbitrary, though it has been many years since I read his …
answered May 10 '12 by David Lewis
5
votes
One Turing machine is more powerful than one pushdown automaton -- that is a fundamental theorem of automata theory and can be proved in a number of ways. For example, the halting problem for TMs is …
answered Mar 22 '12 by David Lewis
8
votes
Hint -- You need to show that your TM has the same power as a finite-state automaton (as the commenter Dave Clarke said), that is, given such a TM, construct a FSA that accepts the same language. B …
answered May 10 '12 by David Lewis