Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

learn more… | top users | synonyms

1
vote
1answer
43 views

Is the empty set/language contained in the following set

Assume I have the following set of languages: $$ \{L \subseteq \{0,1\}^* \mid \text{for all $w \in L$, $|w| \leqslant 3$}\} $$ I know it contains the language containing the empty word since the ...
0
votes
0answers
128 views

Automata to detect numbers divisible by $7$

I have a task and I really have no idea how to solve it. Build deterministic finite automata such that it can detect numbers divisible by $7$. So our alphabet is $\left\{0,1,2,3,4,5,6,7,8,9\right\}$ ...
1
vote
1answer
196 views

Show that the language is regular - Closure

For languages $A$ and $B$, let the perfect shuffle of $A$ and $B$ be the language $$L=\{w \ \mid \ w=a_1 b_1 \dots a_k b_k, \text{ where } a_1 \cdots a_k \in A \text{ and } b_1 \cdots b_k \in B, ...
0
votes
1answer
38 views

Show that the language is regular

Let $$B_n=\{a^k \ \mid \ k \text{ is a multiple of } n\}$$ Show that for each $n \geq 1$, the language $B_n$ is regular. $$$$ Could you give me some hints how we coukd show this?? Do we have ...
0
votes
1answer
61 views

Construct the DFA of the language

I have to construct a DFA for the language $$\{w \mid w \text{ has exactly two } a's \text{ and at leat two } b's\}$$ To construct it we have to construct first the DFA's for the languages $$\{ w ...
0
votes
2answers
178 views

Checking Understanding of DFA Regular Operations - Intersection and Star

I'm currently taking a Logics course, and trying to understand the regular operations, intersection and star. I have a question regarding the work I have done so far. Given the following ...
-1
votes
1answer
57 views

$L_{a}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$ [closed]

Why the following is not context free? Anyone could describe it for me. $L_{a}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$
0
votes
1answer
23 views

Reference for finite state automaton

I am studying Grigorchuk's groups and it involves somewhat theory from Finite state automatons which I have never had any encounter before. Can somebody suggest me what are the best but self readable ...
2
votes
3answers
30 views

Name for a state of an automaton that can't be left

In an automaton, we might have a state that once reached cannot be left. It is for example for Ø in Is there a common/official name for such a state ?
1
vote
1answer
1k views

Construct a Turing-Machine for Factorial(unary)

I am designing a turing machine which calculates the factorial of any given input for example, $3! = 3.2.1$, on tape it will look like this $Blank|1|1|1|Blank$ What I have done so far is that, I made ...
5
votes
0answers
312 views

Designing a turing machine for primality check.

I am designing some turing machines, so far I have made Binary Addition and subtraction. Now I've been thinking that what if turing machine can check if the number is prime or not. Lets suppose we ...
0
votes
1answer
38 views

NFA from regular grammars

I am trying to make an NFA from this regular grammar $$\{a^n \mid n > 0\}\cup \{b^m a^k \mid m\ge 0,k \ge 0\}\;.$$ This is what I have now. The last part, $a\ge 0$, is the one I am not sure ...
1
vote
1answer
71 views

Attractors of a Random Boolean Network?

I need some direction on the topic of Random boolean networks (NK-boolean networks or Kauffman automata). I know some of the results like if K=1 the systems settles down to fixed points, if K=2 it ...
0
votes
1answer
118 views

DFA automaton that recognizes the following language

Need to construct a DFA automation that recognizes the following language of strings over the alphabet {a,b}: The set of all strings that contain the pattern baa and end with b. (So, for example, your ...
3
votes
1answer
3k views

Designing a Turing machine for Binary Multiplication

I need help designing a turing machine that will compute the following $$f(x,y) = x\times y$$ How to approach this problem in binary base? This is a assignment so I don't want anyone to solve it ...
6
votes
4answers
114 views

Can this set of rules perform all Boolean operations?

I never worked in this field before, I just thought about this set of rules and never saw something similar before. I apologise if I don't use the right mathematical vocabulary for my question. ...
0
votes
1answer
125 views

Context Free Grammar and some details [closed]

Why this grammar shows a Context Free and Linear Language, (i.e, not context sensitive or non-context free). S -> SBA | a BA -> AB aA -> aaB B -> b
1
vote
2answers
42 views

Algorith/ Equation to get the ith element in N x N

I am having a difficulty figuring out the equation to get the ith element in $\mathbb{N}\times \mathbb{N}$ ( crossing the set of natural numbers).We have $\mathbb{N}\times \mathbb{N} = \{ ...
0
votes
1answer
53 views

Prove the following context-free language is generated by this grammar.

I would like to prove the context-free language $$ \mathcal{A} = \{ w\#x ~:~ w^R \text{ is a substring of $x$ for } w,x \in \{0,1\}^* \}, $$ has the context free grammar \begin{align*} ...
1
vote
1answer
29 views

Language described by inverting accepting states of NFA

What is the formal language described by inverting accepting states of NFA? By inverting, I mean that rejecting states become accepting states and accepting states become rejecting states. Is there a ...
3
votes
2answers
144 views

Is the language “substrings of an even-lengthed regular language” also regular?

I want to prove that for a regular language $L$ where $\forall w \in L$ the length of $w$ is even, the language containing the first halves of the words of $L$ and the language containing the second ...
1
vote
2answers
93 views

NFA construction problem

I need to construct an automaton that recognizes the following language of strings over the alphabet $\{a,b\}$: The set of all strings over alphabet $\{a,b\}$ with the subsequence $abba$. (A ...
2
votes
1answer
117 views

Designing a Turing machine for $a^n$ $b^{2n}$ $a^n$

I am new to theory of automata, and i have a little knowledge of designing a turing machine, I am stuck in this question which is given to us as an assignment, $\{$$a^n$ $b^{2n}$ $a^n$ : ...
2
votes
1answer
57 views

Intersection of context-free language and its reversal

I know that intersection of two context-free languages is not always context-free and the following problem: Given two context-free languages A and B, is $A \bigcap B \neq \emptyset$ ? is ...
0
votes
1answer
54 views

Closure properties between 2 languages of different types

Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement? I have this Chomsky hierarchy in ...
0
votes
1answer
42 views

Construct an automata for this language

Let $\mathcal{L}_1$ be the language over alphabet $\{0,1\}^*$. Define language $\mathcal{L}_2$, call even-$\mathcal{L}_1$, as: $$\mathcal{L}_2 = \{ w_2 w_4 \ldots w_{k} ~:~ w_1 w_2 w_3 w_4 \ldots ...
0
votes
1answer
43 views

Proving language as regular

Suppose that A and B are languages such that A o B is regular. Suppose that B is regular. Prove or disprove that A is regular. I am having a tough time with questions relating to proving a language ...
1
vote
1answer
96 views

Prove that $\{ww^R\#ww^R\}$ is not context free

I need to prove that $L = \{ww^R\#ww^R \; | \; w \text{ is in } \{a,b\}^*\}$ is not context free. I have tried using the pumping lemma for this. For $w=a^pb^pb^pa^p\#a^pb^pb^pa^p$. I have two cases ...
0
votes
1answer
65 views

Building a Deterministic Finite Automaton with the set {a}

Design a DFA for the set of strings in $\{a\}$* such that it's length is divisible by 3 or 5. The point that I am not understanding is, how many states do we need? Since we can't possibly represent ...
1
vote
0answers
30 views

question about determinstic pushdown automata

i need to show that there is no DPDA accepts the language $L=\{a^n*b^n \mid n>0\}\cup\{a^n*b^{2n} \mid n>0\}.$ i used the prefix property but i'm stuck showing that if $w,w' \in L$, $w$ is ...
1
vote
1answer
368 views

Context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, S -> AB | c A -> aAb | c B -> bBa | c Now correct me if I'm wrong, but if this language has an NFA it ...
1
vote
2answers
46 views

Did I find the right expression for the regular language for this FSA?

I have the following FSA, and the regular language that I found for it: Is this language correct? It doesn't match the solution in the book, but my teacher says there can be multiple equally ...
1
vote
2answers
68 views

How to break down a problem while constructing a CFG for a language?

A problem I came across was: Design a CFG for the language $\{a^ib^jc^k\,|\,i=j+k \}$ The solution I came up with : $S\rightarrow aSc\,|\,S_1$ $S\rightarrow aS_1b\,|\,\epsilon$ It took ...
0
votes
1answer
2k views

Help understanding a 'reversing a string' Turing Machine

I am having a bit of a confusion understanding some transitions in a Turing Machine. Its an example from Introduction to Languages and the Theory of Computation by John C. Martin. I've attached the ...
1
vote
1answer
482 views

Prove that $L=\{a^nb^nc^md^m \mid m,n >=0\}$ is context free language

I'm trying to write the grammar of this language, in order to prove that it is CFL but I'm stuck because m or n could be 0. The language is: $L=\{a^nb^nc^md^m \mid m,n >=0\}$ . If they were ...
1
vote
1answer
78 views

Proving languages are undecidable

Let L5 be the language { {G,D} | G is a CFG, D is a DFA, and L(D) ⊆ L(G) } Show that L5 is undecidable. Is L5 R.E.? Is it co-R.E.? I am not quite sure where exactly to start with this. Could ...
2
votes
3answers
104 views

regular language proof, a language partial to a regular one

So, I've been trying to solve a question I got and I think I'm correct but I'm not positive. Is the language {w| www belongs to L' and L' is regular} regular? I couldnt find any way to prove it isnt ...
0
votes
0answers
27 views

Nondeterministic final automat - example

Show a possibly nondeterministic FA to accept the following language: $$\left\{w\in\{a,b\}^*:w\text{ contains at least one instance of }aaba,bbb,\text{ or }ababa\right\}$$
0
votes
2answers
32 views

Language of Grammar

Let $G = (V,T,S,P)$ be the phrase structure grammar with $V = \{0,1,A,S\}$, $T=\{0,1\}$, and a set of productions $P$ consisting of: $S \to 1S$ $S \to 00A$ $A \to 0A$ $A \to 0$ What is the ...
0
votes
1answer
32 views

Designing a Pushdown Automation to accept a language

Im a novice trying to understand the theory of computation.Im trtying to learn about PDA.I understand that it is a machine counterpart of CFG.Im basically referring to Introduction to Automata Theory ...
0
votes
0answers
42 views

Designing a turing Machine belonging to a language

Im trying to learn the concept of turing machines.I have understood the basic stuff like its a simple mathematical model of a computer and its parts.Now im asked to create a turing machine. ...
1
vote
1answer
116 views

Can 2 items be added/taken away from a stack in push down automata at once?

Here is a language and 2 ways (I hope) of representing it with a PDA. Can I use the notation (b,a $\to$ ee) or anything of the like, to take away 2 items from the top of a list at once? Such as I ...
0
votes
2answers
657 views

Construct a PDA to accept the language

construct a PDA that accepts the language: a) $L_1 = \{ a^k b^k c^i \mid k,i \ge 0 \}$ my answer is : $$\begin{align*} &S\to AA\\ &A\to abc \mid ab \mid c \mid \lambda \end{align*}$$ b) ...
0
votes
2answers
169 views

How to design a Context-Free Grammar and Pushdown Automaton for the following language:

How would you design a context-free grammar for the following language? $\{p^n \ r^m \ p \ \ b^{m+n} \ \ r^2 ∣ m,n\geq 0\}$ Derive a Pushdown Automaton that accepts the same language as the CFG. ...
0
votes
1answer
37 views

Definition of “equivalence classes”

I am studying finite state automata and learning how to prove a machine uses the minimum number of states. I have come across the Myhill-Nerode theorem and one of the corollaries states the following ...
1
vote
0answers
60 views

What is the highest state in the context of finite state automata?

I am doing an assignment for my Theory of Computation course. We are writing a function and I am having a hard time understanding what "highest" state means in the following context: ...
1
vote
1answer
115 views

Automata Language regularity proof by construction.

I've been trying to prove or disprove a question that popped during our last session in Uni, we've been using automaton constructing to prove regularity for a while now and I really do have the handle ...
0
votes
1answer
68 views

For $\sum = \{ 0,1 \}$, $A$ has strings which contain a $1$ in their middle third, and a $B$ which contain two $1$'s in their middle third.

Language $A$ can also be represented as, $$A = \{ uvw \mid u,w \in \sum^*\text{ and, }v \in \sum^* 1 \sum^*\text{ and, }|u| = |w| \ge |v| \}$$ Language $B$ can also be represented as, $$B = \{ uvw ...
1
vote
0answers
330 views

Help with proving a language is regular (Sipser problem 1.49a)

I am working through Sipser's Introduction to the theory of computation on my own, so I don't have access to a teacher. Hopefully you can help me! Giving hints is highly appreciated. This question is ...
1
vote
2answers
236 views

Divisibility problem using DFA

Original problem: Create a DFA for every positive integer $k$, so that when DFA takes a binary string (reading from most significant bit), decides whether the number is divisible by $k$. A DFA for a ...