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

learn more… | top users | synonyms

0
votes
0answers
30 views

Turn DFA into lazy DFA [on hold]

How is the procedure of turning a DFA into a lazy DFA? I do not know anything about the procedure and I can`t find it explained on the web. My second question would be: Is this already a lazy DFA? ...
0
votes
1answer
16 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
33 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
16 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
47 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
11 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
51 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
45 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
48 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
21 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
24 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
26 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
13 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
16 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
28 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
24 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
18 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
12 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
38 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
23 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
51 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
13 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
12 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
26 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 ...
1
vote
1answer
29 views

Constructing a NFA from a right linear grammar, is this correct?

Given the right linear grammar G S -> abA | bbB | a A -> bB | aA | b B -> baB | aaaA | [Epsilon/Terminates] Is the NFA in the image below the proper ...
1
vote
0answers
40 views

Difference between a*b and a*+b? Does the “+” denote Kleene plus or “or”?

Me and a friend are study for a quiz and are trying to determine the difference between the two NFA's produce by the regular exressions a*b and ...
0
votes
2answers
62 views

Designing a deterministic finite automata

How would I go about designing a deterministic finite automata to recognize the language L = {λ, ab, abab, ababab, . . . } consisting of strings that start with ‘a’, end with ‘b’, and alternate in ...
0
votes
1answer
47 views

Deterministic finite automata [closed]

For this question about Deterministic finite automata: Is this answer: bbbb, bbba, bbab, bbaa, b, a correct?
7
votes
1answer
131 views

Challenge on Some Language and PDA

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
0
votes
0answers
26 views

syracuse/collatz variant

Here is a variant of the famous Syracuse/Collatz problem: if you think about the maps $n \to n/2$ and $n\to 3n+1$ as edges in a non deterministic automaton whose states are the integers, so that ...
1
vote
1answer
29 views

Checking correctness of finite state automata designed

How to check correctness of finite state automata we have designed for a regular expression with the help of any computer program or prolog?
0
votes
1answer
27 views

Finite State Automata for (0+11+01)*(0)*(01)*

This is my homework problem and I am struggling hard for it. Can anyone please help me out? I need to find out finite state automata for (0+11+01) * (0) * (01)*. Also, if anyone can please tell me the ...
0
votes
1answer
27 views

Proving non-regularity of a language

How can I prove $L = (01^n2^n | n\geq 0)$ is not regular? Would it be sufficient to say that $01^p2^p$ is in $L$ and by pumping lemma, $01^p2^p$ can be written as $xyz$ such that $|y|>0, ...
1
vote
1answer
46 views

equivalence class for language in Theory of automata

we say x,y is equivalent to language L, if for any $z \in L$ we have: $xz \in L \Longleftrightarrow yz \in L$. for $ L= (ab \cup aab)^* $, what is the equivalence class for L? my professor ...
0
votes
2answers
86 views

Input and output of a Turing machine

For some machine models of computation there is no question what their input and output is: it's just the contents of some specific "cells", e.g. on a "tape" isomorphic to $\mathbb{N}$. Consider for ...
0
votes
1answer
24 views

Use the power-set construction to find a deterministic automata

Given a nondeterministc automata N, how do you use the power-set construction to find a deterministic automata that recognizes L(N)? Here is my work so far: We can start in state 1, 2. If we get ...
-1
votes
2answers
24 views

How to prove that graph with 2 or more nodes has atleast 2 nodes which have same degree? [closed]

One of my instructor gave me a hint to use Pigeon-Hole principle, but I dont know how to apply this into this question.
2
votes
1answer
26 views

Why is $\left\{a\right\}^*\cap L(A)=\emptyset$? where $\delta(q,a)=q$

I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below : Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all states ...
0
votes
1answer
37 views

how to draw this DFA?

{w belongs to all string patterns as a^i b^j a^k | i+j=even and j+k =odd} draw a DFA and find its regular language. please note here, i have put comma in between the format of aba string just for ...
0
votes
0answers
34 views

contradiction of pumping lemma on even palidrome language's completion

I have the language of all the words that are not even length palindromes, or more formally: $L= \{ w: \forall u\in\Sigma^*, w\ne uu^r \}$. And I need to prove that the Pumping Lemma for regular ...
0
votes
1answer
28 views

How can a DFA corresponding to an NFA have a transition that the original NFA does not?

First sorry for the poor pictures, but I think they are ok enough to get the point across. I would like to see the steps involved to convert this NFA to a DFA using the method explained in this ...
0
votes
1answer
15 views

Soft question, Understanding NFAs and DFAs; Requirements for either.

I have a few quick questions about NFAs and DFAs. Is any automaton with epsilon transitions always a NFA? Is any automaton with two paths for the same symbol from a state always a NFA? Ex. Say state ...