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

learn more… | top users | synonyms

2
votes
1answer
403 views

Is $\epsilon$ in every alphabet?

Given a $\Sigma$ an alphabet, is $\epsilon$ in it logically? For example, if I have a function $ f : \Sigma \to \Sigma $, can I define it for example $ f(\sigma) = \epsilon$? even if my alphabet is ...
2
votes
1answer
51 views

CF grammar on this language

I'm trying to write a context-free grammar for this language: $L = \{a^n b a^m (bb)^n : m \ge 1, n \ge 0\}$ I was getting lost with maintaining $n$ number of $a$'s and $(bb)$'s and I'm not sure how ...
2
votes
1answer
90 views

NFA from grammar productions

Based on this grammar: \begin{align} G = (\{S,A,B\}, \{a,b, c\}, S, P) \end{align} \begin{matrix} \\P: \\S → abaS | cA \\A → bA | cB | aa \\B → bB | cA | bb \end{matrix} I created this NFA: ...
2
votes
2answers
117 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 ...
2
votes
1answer
113 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 ...
2
votes
1answer
116 views

Definition of a deterministic Pushdown automaton

According to my book the definition of a deterministic Pushdown automaton allows for $\delta(q,\epsilon,Z)$ to be non-empty if $$\forall\sigma\in\Sigma:\,\delta(q,\sigma,Z)\neq\emptyset$$ Can someone ...
2
votes
2answers
705 views

Checking if the language is a regular one

Let A = $\{x \in \{a,b\}^{*} \mid |x|_{a} = |x|_{b} \}$. Is possible to find a regular expression $\alpha$ such that $L(\alpha)$ = A ? $L(\alpha)$ is the regular language defined by $\alpha$. It ...
2
votes
1answer
754 views

Unable to construct Context-free Grammar from Pushdown Automaton

I have a problem in constructing a Context-free Grammar for the Language $$L = \{a^mb^n : m≠n,m>0,n>0\} .$$ Though I can able to construct a Pushdown Automata. I can construct a CFG, but it ...
2
votes
2answers
4k views

Construct PDA that accepts the language $L = \{ a^nb^{n + m}c^{m}: n \geq 0, m \geq 1 \}$

Problem Construct PDA that accepts the language $L = \{ a^nb^{n + m}c^{m}: n \geq 0, m \geq 1 \}$ My initial idea was, If we read an $a$ push a $x$ onto stack If we read a $b$, there are two ...
2
votes
1answer
2k views

Nondeterministic Finite Automata to Deterministic Finite Automata?

I am unfamiliar with the general process of converting NFA to DFA. I have general understanding of the theory, but I don't have the method established. Please help explain the process required to ...
2
votes
1answer
32 views

Accurate model of a laptop when it is not connected to any external device

You have a laptop with a fixed amount of memory and hard disk space and no external storage devices connected (CD, USB drives, . . . ). Which of the following is the most accurate formal model of your ...
2
votes
1answer
74 views

Show a language is regular with Myhill-Nerode Theorem

I understand how to show a language is not regular using Myhill-Nerode Theorem (proof by contradiction), but how do you show the language is regular? Take language $0^*1^*$ for example. I know this ...
2
votes
1answer
71 views

What are annihilators?

I was recently listening to Automata lecture, there it was told told that an empty set is an Annihilator for concatenation just like $0$ is for multiplication. What do we mean by this statement?
2
votes
2answers
358 views

What are closure properties of regular languages?

In class we've been talking about DFA's and NFA's and being closed under ____. The homework problems say to "use closure properties of regular languages to show that a regular languages are closed ...
2
votes
2answers
57 views

Is the language $\{yxzx^Ry^R \mid x,y,z \text{ belongs to } \{0,1\}^+ \} $ regular?

This is a question from Iran's national grad school entrance exam. In the answers key, the answer was that the following language is regular but I doubt it is true, I proved using pumping lemma that ...
2
votes
1answer
170 views

Concatenation of Finite Languages and Regular Languages

I know that the following statements regarding Concatenation are false. However, I'm having difficulty explaining why they are false with simple counter-examples. I'm able to find simple ...
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 ?
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 ...
2
votes
1answer
55 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 ...
2
votes
1answer
39 views

Stack automata with nonequality

I encontered the following problem that I'm unable to solve. The goal is to construct a stack automata, that accepts language $$ L = \left\{u\mathrm{\underline{c}}v \mid u,v \in ...
2
votes
1answer
100 views

Decide whether DFA accepts all Strings

Wikipedia : Because DFAs can be reduced to a canonical form (minimal DFAs), there are also efficient algorithms to determine: whether a DFA accepts any strings. whether a DFA accepts all strings. ...
2
votes
1answer
67 views

A correct proof for this pumping lemma example?

Given the language $L = \{0^{2^n} | n \geq 1\}$ So, the language contains all strings that have $2^n$ $0$s. First of all I take $z = a^{2^p}$ where $p$ is the constant guaranteed by the pumping ...
2
votes
2answers
940 views

Why is a 3-PDA no more powerful than a 2-PDA?

A k-PDA is a pushdown automata with k stacks. My textbook on Computation Theory has an exercise that asks to prove that 3-PDA is no more powerful than a 2-PDA. Now consider the language that I made ...
2
votes
1answer
83 views

(Transformation) Semigroups, the semigroup $\mathbf D_n$ and the wreath product

I have some trouble understanding the following proof, were I can't even figure out how some terms are defined. But first I state some definitions and preliminary lemmas. A transformation semigroup ...
2
votes
1answer
151 views

Reducing A$_\text{TM}$ to REGULAR$_\text{TM}$

We can solve A$_\text{TM}$ problem using REGULAR$_\text{TM}$. Assume $R$ is a Turing machine that decides REGULAR$_\text{TM}$. We construct $S$ to decide A$_\text{TM}$ as follows On input ...
2
votes
1answer
535 views

DFA Rejection State

I'm being asked to construct a DFA for the language over $\{0,1\}$ such that each string of five consecutive symbols contain at least two zeroes. In my construction, it seems to me that it would make ...
2
votes
1answer
51 views

Proving that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular. [duplicate]

I am trying to prove that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular, whereas: $\Sigma=\{a,b\}$. I tried to use the pumping lemma with no success. I have also tried to ...
2
votes
1answer
878 views

Turing Machine for comparing, copying, and operating

If one wants to design a Turing Machine for a function such as this: Where $x>0,y>0$ and are both integers represented in unary, so an example movement in this TM on the read-write head would ...
2
votes
1answer
407 views

DFA Transition Function Inductive Proof

Show for any state $q$, string $x$, and input symbol $a$, $\hat\delta(q, ax) = \hat\delta(\delta(q, a), x)$, where $\hat\delta$ is the transitive closure of $\delta$, which is the transition function ...
2
votes
1answer
786 views

Does closure under the union and concatenation operations imply closure under the star operation?

Given any two languages $A$ and $B$, recall the following regular operations: Union: $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$ Concatenation: $A \circ B = \{xy \mid x \in A \text{ ...
2
votes
2answers
62 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 ...
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 ...
2
votes
1answer
713 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
73 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 ...
2
votes
2answers
601 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 ...
2
votes
2answers
4k views

Pushdown automata for the language $\{ w001w^\text{R} : w = \{0,1\}^* \}$

I'm trying to make a PDA that accepts the language $\{ w001w^\text{R} : w = \{0,1\}^* \}$ by empty stack. (Here $w^\text{R}$ denotes the reverse of the string $w$.) Our stack symbol s $\#$. I've come ...
2
votes
2answers
2k views

Existence of NFA of a reverse of a language

Hi, I'm really stuck on how to prove the following: Given that $L$ is a language and $L'$ is a set such that $L' = \{w \mid w' \in L\}$ where $w$ is the reverse of $w'$, e.g., if $w = a a b$ then $w' ...
2
votes
2answers
53 views

Derivation of a property of a language

I am confused how this relation is derived for a language on alphabet V A,B The relation is $$ (A\cup B)^*=(A^*B^*)^* $$ I am confused how this is derived. Any pointers?
2
votes
1answer
85 views

Is $f$ is computable by a finite automaton, the dual of $f$ is thus computable also?

et $A$ be a finite alphabet. Let $A^*$ denote the language of all words in $A$, and $\epsilon$ the empty word. Let $\rho : A^* \to A^*$ denote the "reverting" map, that transforms $a_1a_2\ldots a_n$ ...
2
votes
1answer
117 views

Conditions for: $xy=zw$ and $yx=wz$

Let $x,y,z,w$ be finite strings. Find the necessary and sufficient conditions for the following two equations to hold simultaneously: $$xy=zw$$ and $$yx=wz$$ Automata Theory is new to me and i am ...
2
votes
1answer
148 views

Two elementary question on automaton and language

1.What is the definition for a semigroup(or monoid) recognizing a set of words(or language)?2.Are recognizable,rational and regular equivalent to each other with respect to a language? PS:The reason ...
2
votes
1answer
1k views

Nondeterministic PDA to Deterministic PDA

Are there any resources on how to convert a non-deterministic PDA to a deterministic one, if a deterministic PDA actually exists? Or is there a step by step way on how to do this, kind of like going ...
2
votes
1answer
964 views

Construct PDA that accepts the language $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^*, w_1 \neq w_2^R\}$

Problem Construct PDA that accepts the language $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^*, w_1 \neq w_2^R\}$ For the language $wcw^R$, it's much easier because the stack is always empty after ...
2
votes
2answers
160 views

Is it possible to prove that $L$ is a regular language?

Let $L = \{a^{f(m)} | m \geq 1 \}$ where $f: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ is monotonically increasing and complies that for all $n \in \mathbb{Z}^+$ there is $m \in \mathbb{Z}^+$ such that ...
2
votes
1answer
300 views

Generating all words in a language from CFG

I have a non-ambiguous context-free grammar. Is there some standard algorithm to create list of all the words in the language the CFG defines? This can be done with an abvious brute-force search by ...
2
votes
1answer
31 views

Turing Machine Diagram, one Solved Problem ?!

The following Diagram Gets binary number $x$ and produce $x+1$. complete it: the book solution is says first line is the answer. any hint or idea for completing this TM?
2
votes
1answer
31 views

Let $Σ=\{a,b,c\}$. Which of the following statements is true?

$1)$ For any $A\subseteq\Sigma^*$, if $A$ is regular, then so is $\{x∣ xx\in A\}$. $2)$ For any $A\subseteq\Sigma^*$, if $A$ is context-free, then so is $\{x∣xx\in A\}$ According to me the ...
2
votes
1answer
80 views

Let M range over turing machine descriptions .Consider the set REG={M|L(M) is a regular set} which of the statements are true?

The complement of REG is Co-REG REG is recursively enumerable but Co-REG is not REG is not recursively enumerable but Co-REG is Both are recursively enumerable 4.None of them are recursively ...
2
votes
1answer
99 views

what are the practical uses of “game of life” or “langton's Ant”

A few questions: Besides looking really cool, what are the practical uses of "game of life" or "langton's Ant"? I understand how agent-based modeling itself is a potentially useful methodoly, not ...
2
votes
2answers
83 views

Finite automata as dynamical systems

In abstract (deterministic finite) automata theory the set of states of an automaton is an arbitrary set Q, and the transistion function is a specific set δ ⊆ Q × Σ × Q (with alphabet Σ, i.e. another ...