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

learn more… | top users | synonyms

0
votes
0answers
13 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
16 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
27 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
0answers
20 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 ...
-2
votes
0answers
24 views

Definition and applications of Push Down Machines [on hold]

What are push down machines? Please explain in simple and short. What are the applications of push down machines ? Is DTM and NDTM are its applications ? If not then what they are ?
1
vote
1answer
10 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 ...
0
votes
0answers
38 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
34 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
13 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
18 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
18 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
14 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
14 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. ...
0
votes
0answers
30 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
35 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
46 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
25 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
49 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
20 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
17 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 ...
0
votes
0answers
34 views

Why Algorithm is not is exist for understanding RE

I am reading Daniel I. Cohen book of computer theory. Here, he wrote that the recursive definition of regular Expression is easy to interpret a language, However, don't provides the way how to ...
1
vote
0answers
19 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 ...
0
votes
0answers
11 views

Turing machine that modifies each cell that contains a certain input one time at most

If I have a single tape turing machine running on some input $x$, where it modifies each part of the tape with $x$ one time at most...would the TM be decidable? Any advice or guidance appreciated; ...
1
vote
2answers
54 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 ...
0
votes
0answers
12 views

What is sense of $In(\phi)$ in Rabin's theory of SO-decidability?

In M.O. Rabin's article Decidability of second-order theories and automata on infinite trees in section dedicated to automata on infinite trees there is definition of $In(\phi)$ function: For a ...
0
votes
0answers
53 views

Formal Languages and Automata proof

$L$ and $K$ are subsets of $A^*$ where $A$ is an alphabet. Prove that $(L^* K^* )^* = (L \bigcup K)^*$ where $L^*=(L^0)\bigcup (L^1)\bigcup (L^2)\bigcup \ldots$ and ...
1
vote
0answers
50 views

Pumping Lemma for Context Free Languages: Is this language CFL?

I am learning for the first time the Pumping Lemma for CFL, and I thought I understood how it works until I came across this example: "Show that $L = \{a^m b^m c^n \mid m \leq n\}$ is not a CFL." My ...
2
votes
1answer
18 views

Turing machine that goes left on first symbol

I have a turing machine with transitions given by the following table I'm inputting the string aaaa. So if I look at the first symbol "a" in state A, it says to replace it with an X, go into state ...
1
vote
1answer
51 views

How to prove that a language `L` is not a regular language?

Given the following question: Prove that the following language is not a regular language: A language L in alphabet $\Sigma = \{a, b\}$ where every word ...
0
votes
2answers
24 views

State diagram of DFA

I'm trying to understand how to create state diagram of DFA. I found following example. On the first diagram I dont understand why we need fourth state when third state is final and there is no ...
1
vote
0answers
15 views

how to create transition system/automata for modulo 4

I don't know how to think when to build a transition system/automata to calculate modulo 4 a of binary numbers. I know that the last two binary digits gives the rest but I need to go through hole ...
0
votes
1answer
30 views

Create DFA that accept language where number of 0's is even and after every 1 goes 0

Alphabet = {0,1}. Language L = {word w | number of 0's in w is even and after every 1 goes 0}. I'm trying to create DFA that accepts language L. But I have some ...
2
votes
0answers
29 views

Size of automata or regular expressions avoiding cross patterns

Let $\Sigma$ be an alphabet of finite size $k$, and $n$ some integer. I am interested in the language of words of size $n$ that do not contain $abab$ as a subword, for any pair $(a,b) \in \Sigma$ (I ...
1
vote
1answer
16 views

Is it possible to build an Pushdown Automata for an Ambiguous Context-Free Grammar?

Say I have the following grammar: $$S \to \epsilon \mid [S] \mid (S) \mid SS$$ This grammar is ambiguous as both the following parse trees yield the empty string $$S \to \epsilon$$ $$S \to SS \to ...
0
votes
1answer
18 views

Nondeterministic finite automaton understanding problem

It is probably a silly question but I have problem understanding it. Let's say I have to design a nondeterministic finite automaton that accepts the language consisting of words containing a string of ...
0
votes
1answer
29 views

Pushdown automaton design

I have to design a PDA that recognizes the language: $$L=\{w \mid \#(a,w) - 3\#(b,w) = 2\} $$ where $\#(a,w)$ means the number of letters $a$ in $w$ My idea is to count $a$'s and $b$'s. I have to ...
0
votes
0answers
29 views

How do I show language of composite number of x's not context-free?

I want to know if {0^k | k is a composite number} a context free language?? If , it's not,can anyone give me its proof by pumping lemma, I'm just unable to figure it out..
0
votes
1answer
20 views

Show a Turing Machine accepts all DFAs

You have a Turing Machine $T = \{ \{ A \} \mid A$ is a DFA and $L(A) = \Sigma^* \}$ i.e. the DFA that accepts all languages. Show it's decidable. Can you use the complement of this, the DFA that ...
0
votes
0answers
17 views

Constructing a nondeterministic automaton from deterministic

Construct a nondeterministic finite-state automaton that recognizes the language generated by the regular grammar G = {V,T,S,P} where V = {0,1,S,A,B}, T = {0,1}, S is the start symbol, and the set of ...
0
votes
1answer
39 views

Deterministic finite automaton algorithm

I am having a little trouble understanding this question. For a DFA M = (Q, Σ, δ, q0, F), we say that a state q ∈ Q is reachable if there exists some string w ∈ Σ∗ such that q = δ∗(q0, w). Give an ...
0
votes
1answer
24 views

Pumping lemma to prove that a language is not context free

We've got $L = 0^{x^{2}}$. So we let $w = 0^{p^{2}}$, and we know that we can split w into $w = u\cdot v\cdot w\cdot x\cdot y$ , according to the pumping lemma for CFGs. I'd like to know how to ...
0
votes
1answer
58 views

CFG and PDA for w1#w2

Looking for a Context Free Grammar and Push Down Automata to describe a language made of two words, separated by a #, where the first words is not equal to the second word. For this example, we can ...
1
vote
0answers
33 views

Is this correct way to prove that { $uv$ $\mid$ $u$ and $v$ are strings over $(0,1)$ & $|u| = |v|$ } language is not regular?

I proved this using Pumping Lemma in the following way, Taking $p$ as pumping length then let us take a string $S$ where, $|u| = |v| = p$ Now according to pumping lemma $S$ can be split into three ...
0
votes
1answer
61 views

How to prove that $ \{ 0^n 1^{5n} : n \ge 10000 \} $ is not a regular language?

I proved that $$ \{0^n 1^{5n} : n \ge 0\} $$ is not a regular language using Pumping Lemma by following way. Solve by contradiction that $ L = \{ 0^n 1^{5n} : n >= 0 \}$ is regular language. ...
0
votes
0answers
15 views

Converting the NFA produced from the language $a^nb^n : n\geq 0$ to a DFA to show its regular? Leading to question about pumping lemma.

I am reading about the pumping lemma, and having a hard time understanding it. I noticed that it is used to prove a language is not regular by contradiction. So you must first prove that a language in ...
0
votes
0answers
13 views

Showing that $f(K) = {f(a) : a ∈ K}$ is recursively enumerable

Today we went over things that are recursively enumerable, but I cant seem to grasp how to prove the equation $$f(K) = {f(a) : a ∈ K} $$ is recursively enumerable. I can prove that equations are ...
0
votes
1answer
32 views

Construct finite Automata

Im trying to construct finite automata in the form of diagrams accepting certain languages. One is in all parts the alphabet is {a, b}. Construct FA {w| w has neither aa nor bb as a subword} I ...
0
votes
1answer
22 views

Building PDA for a Language

I won't deny that this is not my homework question, but I've been thinking for a couple of hours and still have no understand $L = \{w | w ∈ \{0, 1\}^*\}$, w is a list of unary integers separated by ...
0
votes
1answer
27 views

abstract machine, what language does M accecpt?

What language does M accept? 1: {a}3 ∪ {b}3 ∪ {λ} 2: {a}3 ∪ {b}3 3: {a, b}3 ∪ {λ} 4: {a, b}3 ∪ {λ} I'm not completely sure just yet which one would work. I would appreciate it if ...
0
votes
1answer
27 views

Push Down Automata that recognizes language

I'm struggling on how to use the stack for this push down automata problem. The problem is to design a PDA that recognizes the language: $$A = \{a^ib^{2i}|\,i>0\}$$ So, we will be pushing a's onto ...