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

learn more… | top users | synonyms

0
votes
1answer
162 views

Is this language regular?

Given $m,n∈Z$, A is a finite alphabet set ,and $L=\{(a^m,a^n)\}^*$ is subset of $A^*\times A^*$ . Is this language regular ? For example, is $L=\{(a^3,a^7)\}^*$ regular ? Here L is not the set ...
1
vote
2answers
162 views

Whether $L=\{(a^m,a^n)\}^*$ is regular or not?

I am condidering the automatic structure for Baumslag-Solitar semigroups. And I have a question. For any $m,n \in Z$, whether the set $L=\{(a^m,a^n)\}^*$ is regular or not. Here a set is regular means ...
2
votes
2answers
57 views

Regular composition of non-regular language

I've got the following problem: Let's take language $L$. Is it posible that $L$ is not regular itself, but it's composition $L\cdot L$ becomes regular? I suspect that's correct, yet I ...
1
vote
1answer
942 views

Proof that equal-length-concatenation is a context-free language?

If A and B are languages, define A⋄B={xy | x ∈ A and y ∈ B and |x|=|y|}. For example, if A = {00, 101, 111} and B= {1, 11, 00110}, we would have A⋄B={0011}. Show that if A and B are regular, ...
0
votes
2answers
75 views

Algorithm for a regular expression

This was a question for an exam that I received 0 points on, I'd like to get some input on what the correct answer should have been. Imagine that you are asked to write an algorithm P that takes a ...
2
votes
3answers
1k views

Find push down automata and context free grammar

I have the following language: $$ L = \{a^nb^{2n+1} \mid n \ge 0\} $$ I must find the push down automaton and a context free grammar for the language. For the push down I have no idea how to ...
1
vote
1answer
115 views

Give a regular grammar for L

Give a regular grammar for L= {a^n b^n : n<=100} I would do something like this : S---> A | empty string A---> aB| empty String B---> Ab but How do we keep count of the number in the grammar? ...
1
vote
2answers
228 views

regular expression

I would like to write the regular expression for the set of all binary strings where there are no three consecutive 0's. The following strings are part of the language: ...
0
votes
2answers
224 views

Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular.

Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular. It seems to use one Lemma: Pumping Lemma.
3
votes
2answers
172 views

Automata: 1=2, 2= 26, 3=1054, 4=5768, 5 =139314069504, 6 = ???

I am in my own Automaton (finite-state deterministic automata) research, so i have four sets of automata. 2 states automata, 3 states, 4 states and 5 states. Input alphabet $\{0,1\}$ so... the ...
0
votes
1answer
46 views

Given a DFA $\mathcal{M} = (S, \Sigma, q_0, \delta, F)$, is there an algorithm that finds the pumping length of $L(\mathcal{M}$)?

This question has been bugging me for a while, and I'm curious what such an algorithm would look like, if it exists. My guess is that it does exist, but I'm not sure how it would look.
2
votes
2answers
168 views

An NFA with $\Sigma = \{1\}$ with $x^2$ accepting runs on strings $1^x$ for all $x \geq 0$ - how to construct?

One of my homework assignments requires us to construct an NFA over the alphabet $\{1\}$ which has exactly $x^2 + 3$ accepting runs over the input string 1^x for all $x \in \mathbb{N}$. Now, the +3 ...
1
vote
1answer
121 views

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^k| j \gt i+k\} $?

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^k| j \gt i+k\} $? My attempt: $G_1 = (\{ S,A,B\}, \{a,b\},P,S)$ where $P$ consists of: $$ S\to AbBC $$ $$A \to ...
1
vote
1answer
176 views

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $?

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $? I don't have much idea how to approach this one. Could some help me to understand how to approach these ...
1
vote
0answers
376 views

Turing Machine question, this is NOT HW

I was having a hard time understanding and solving this question that wants me to show the final tape and figuring out if whether or not the turning machine accepts it or not. I have a list of 20 ...
-1
votes
1answer
271 views

Decidability/Undecidability Question

Could someone please help me with this question? I'm really having a hard time understanding reductions and decidability. Prove that the language $$L = \{\langle M,N \rangle \mid M,N\text{ are Turing ...
2
votes
1answer
135 views

DFA worst case states

Suppose an NFA which accepts language of the form L(N) = {w| w has 1 in n$^t$$^h$ from last symbol.} Then the corresponding DFA would have 2$^n$ states(worst case of subset construction). If we are to ...
1
vote
1answer
671 views

Proving Language accepted by DFA

I am stuck with a problem, as my proving skills aren't good(trying to improve). Prob: Given a State Table of DFA, decribe what language is accepted, and prove by induction it accepts that language, ...
0
votes
0answers
96 views

Pumping Lemma length, $K$ for context-free language

Please help me understand, and if possible, tips, to determine a pumping length $K$. Suppose I have the example : Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,T\}$, set of ...
0
votes
1answer
147 views

Decidability of a Turing machine always halting in at most ten steps

I've exam comping up soon and I need help with this. Consider the problem: Given a Turing machine $M$, determine if $M$ halts in at most ten steps on every input. Is this decidable? Prove your ...
2
votes
1answer
469 views

Show that this language cannot be accepted by a deterministic push-down automaton [duplicate]

How do you show that there exists no DPDA that accepts $ L = \{0^n1^n \} \cup \{ 0^n1^{2n}\}$ ?
2
votes
1answer
68 views

Constructing PDA with either one state or two states

If $L$ is a context-free language and $\epsilon \notin L $, how do you show that there exists a PDA that accepts the language by final state such that it has not more than two states and makes no ...
0
votes
1answer
419 views

Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3.

I have exam coming up and I need help with this: Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3 Thank you :)
2
votes
2answers
111 views

Giving a regular grammar for the language

I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve ...
1
vote
2answers
2k views

Concatenation of 2 finite Automata

I have some problems understanding the algorithm of concatenation of two NFAs. For example: How to concatenate A1 and A2? A1: ...
1
vote
1answer
51 views

Can every regular language have a linear bounded automaton

As the question states: I am trying to understand automata. Can every regular language have a linear bounded automaton?
2
votes
1answer
98 views

Is there a problem with this example?

In example $1.14$ on page $51$ (of the book and $64$ of this link), shouldn't the string $01000$ get rejected? However it seems that the first three digits of the string would force it to an accept ...
1
vote
4answers
164 views

Non-Deterministic Turing Machine Algorithm

I'm having trouble with this question: Write a simple program/algorithm for a nondeterministic Turing machine that accepts the language: $$ L = \left\{\left. xw w^R y \right| x,y,w \in \{a,b\}^+, ...
1
vote
1answer
767 views

Turing Machine Variation

Hi i'm trying to figure out this question: Give a formal definition of multihead-multitape Turing machine. Then show how such a machine can be simulated by a standard Turing machine Can someone ...
4
votes
3answers
3k views

Finite automaton that recognizes the empty language $\emptyset$

Since the language $L = \emptyset$ is regular, there must be a finite automaton that recognizes it. However, I'm not exactly sure how one would be constructed. I feel like the answer is trivial. ...
2
votes
2answers
161 views

Describe a PDA that accepts all strings over $\{a, b\}$ that have as many $a$’s as $b$’s.

I'm having my exam in few days and I would like help with this Describe a PDA that accepts all strings over $\{ a, b \}$ that have as many $a$’s as $b$’s.
4
votes
2answers
512 views

Push down automata problem

Informally describe the Nondeterministic PDA that generates: $$\{x\#y\ \mid x,y\in\{a,b\}^{*}\text{and}\space x\ne y\}$$ My initial plan was to use nondeterminism to go through each character before ...
0
votes
1answer
46 views

Automata: Proof

Here is the problem: Consider a NFA, M = (K, Σ, Δ, s, F) with (p, a, q) ∈ Δ. Prove that (pʹ, aw) ⊢∗ (qʹ, w) for any w ∈ Σ∗, q′ ∈ E(q) and p′ with p ∈ E(p′). Thanks in advance.
8
votes
1answer
295 views

What is the class of languages accepted by DFAs whose transition monoids are transitive permutation groups?

In the Wiki page A permutation automaton, or pure-group automaton, is a deterministic finite automaton such that each input symbol permutes the set of states. ..... A formal language is p-regular ...
2
votes
2answers
504 views

If $L$ is regular, prove that $\sqrt{L}=\left\{ w : ww\in L\right\}$ is regular

Let $L$ be a regular language. Prove that $\sqrt{L}:=\left\{ w : ww\in L\right\}$ is also a regular language. I suppose I need to modify state machine for $L$ to accept $\sqrt{L}$, but I've been ...
3
votes
2answers
156 views

Is this proof using the pumping lemma correct?

I have this proof and it goes like this: We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$. Then, the following proof is given: There is a $p$ ...
2
votes
2answers
386 views

Regular Languages Algorithm?

I need help proving the following question: Let $L$ be any regular language on $\sum{a,b}$. Show that an algorithm exists for determining if L contains any strings of even length. So far, I know ...
3
votes
1answer
184 views

Context Free Language? Proving through grammar?

I need help solving this question: Is $L = \{ w \in \{a,b,c\}^* \mid n_a(w) = n_b(w) = 2n_c(w)\}$ a context-free language? That is the number of $a$'s equal the number of $b$'s equal twice the ...
3
votes
2answers
96 views

If $L\in REG$ then $M$ has a finite number of distinct rows

Let $L \subseteq \Sigma^{\star}$ and let $M^{\Sigma^{\star} \times \Sigma^{\star}}(\{0,1\})$ an infinite matrix such that for each $x,y\in \Sigma^\star$: $$ m_{x,y}=\begin{cases} 1 & x y\in L\\ 0 ...
0
votes
1answer
99 views

Questions about DFA with Sigma* exiting arrow and RE

Assume Sigma* contains all english alphabet chars. Then in my DFA, I have an exiting arrow of Sigma* and another exiting arrow of "a"(symbol from the alphabet) from one state. Will this be a valid ...
0
votes
1answer
285 views

An infinite context free language can be split into two infinite regular languages

Prove or disprove Let $L$ be an infinite context free language. Show that there exists a regular language $R$ such that $ L \cap R $ and $L \cap \overline{R} $ are infinite and regular.
-1
votes
2answers
88 views

Is λ={λ} true or not

I know that λ={λ} is true i want to know How can i prove that λ={λ} is true or not? Thanks in advance.
1
vote
3answers
699 views

Is indistinguishability an equivalence relation?

Let x and y be strings and let L be any language. We say that x and y are distinguishable by L if some string z exists whereby exactly one of the strings xz and yz is a member of L; otherwise, ...
3
votes
1answer
436 views

Would the following NFA accept all strings?

The question asks the following: "Let N be a nondeterministic finite automaton with s states. Suppose than N accepts all strings of length s or less. Does it follow that N accepts all strings? (If so, ...
1
vote
1answer
209 views

How would I go about proving for this NFA?

I am struggling on this one question, where it is asking to define an XOR automata which is defined as an NFA and it is defined as the following: N accepts the string x if the number of distinct ...
3
votes
2answers
508 views

Question about regular languages and finite automata

We say a language $L$ is regular if it is accepted by some finite automaton $M$. I would like someone to clarify this definition. Given a finite automaton $(Q, \Sigma, \delta, q_0, F)$, we define the ...
0
votes
1answer
71 views

How can I prove a DFA accepts a certain mininum number of states?

We know that if there are two languages, L1 and L2, if L1 and L2 are regular, the intersection of those two is also regular. Suppose we have two machines, M1 and M2, and using them, a new machine M3 ...
1
vote
2answers
209 views

Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1…w_m$?

DFA Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1...w_m$? For part 2, wouldn't it require M states if the word length is M?
1
vote
1answer
371 views

Finite state machine to report when the last 4 inputs were 1011

Suppose you want to construct an FSM containing one input and one output. Consider the example: The machine should assert the input (set to 1) when the last four bits taken in as input match the ...
2
votes
2answers
2k views

suffix regular language

Can someone give me an idea how to prove this: suffix(L) = {y | xy $\in $ L for some x $\in$ $\Sigma$ *}. Or suffix is the set of all suffixes of its strings. Prove that if L is regular, then so is ...