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

learn more… | top users | synonyms

0
votes
0answers
26 views

Automat to detecting numbers divisible by $7$

I have a task and I really have no idea how to solve it. Build deterministic finite automat such that it detect numbers divisible by $7$. So our alphabet is $\left\{0,1,2,3,4,5,6,7,8,9\right\}$ Our ...
1
vote
1answer
24 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
23 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
19 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
38 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 ...
3
votes
1answer
32 views

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

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}\}$
6
votes
1answer
129 views

inherently ambiguous languages

why the second language is a inherently ambiguous languages? anyone could clarify me? L={$a^nb^{2n}c:n\geq 0$} $\cup ${ $a^{2n}b^{n}d:n\geq 0$} L={$a^nb^{m}c^p:n\neq m$} $\cup ${ $a^{n}b^{m}c^p:m ...
0
votes
1answer
20 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
19 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 ?
0
votes
0answers
8 views

Design a Two-Tape Turing Machine which generate Palindrome

For e.g I have a String on a tape, $Blank|1|0|1|0|Blank$. Now I have to Use two tape and Reverse this string into second tape. First tape =$Blank|1|0|1|0|Blank$. ...
0
votes
0answers
24 views

Design a Turing machine to check whether an input is prime or not. [duplicate]

This is an assignment, I need to make a primality checking turing machine, which check whether an input is prime or not. what i've done so far is that i made this logic which is, ...
2
votes
1answer
57 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 ...
2
votes
0answers
58 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
12 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 ...
0
votes
1answer
11 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 now some of the results like if K=1 the systems settles down to fixed points, if K=2 it ...
0
votes
1answer
30 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 ...
2
votes
1answer
59 views

Designing a Turing machine for Binary Multiplication

I need help designing a turing machine that will compute the following f(x,y) = x*y How to approach this problem in binary base? This is a assignment so I don't ...
6
votes
4answers
63 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. ...
1
vote
1answer
89 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
25 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} = \{ ...
1
vote
1answer
69 views

Some inference in Automaton and Decidable Problems

Anyone could correct me that the following inference is True: ( G is a Context Free Grammar) There is an algorithm that decides whether the complement of $L(G)$ (language generated by $G$) is empty ...
0
votes
1answer
25 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
20 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
55 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
35 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
37 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
28 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
0answers
14 views

Manufacturing process automaton (drilling, cutting…)

I'm studying for an exam and in one of the previous exams there was this question: A flexible manufacturing system can perfonn two types of operations: cutting and drilling. There are three types ...
0
votes
1answer
20 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
33 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
40 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 ...
0
votes
2answers
54 views

Proving L is a regular language?

I am having tough with problems like this. Can someone help me. Let L be the set of all strings that are not in the English language. Is L regular?
1
vote
1answer
40 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
17 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
27 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
50 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
30 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
36 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
42 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
41 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
53 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
45 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
21 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
0answers
23 views

What does it mean for an equivalence class to straddle a set of states?

In the following question, what does it mean for an equivalence class to straddle a set of states? Assume you currently have two equivalence classes Φ and Ψ. In addition you have a set of ...
0
votes
2answers
22 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
23 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
24 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
55 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
66 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
60 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. ...