# Tagged Questions

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

3k 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 ...
1k views

### Turing Machine Vs Linear Bounded Automata

Example of language accepted by Turing Machine but not by Linear Bounded Automata ? Is there any EXPSPACE language?
53 views

### How can I implement a Deterministic finite automaton which accepts strings having specific words.

I am trying to make a Deterministic finite automaton which accepts those strings having two specific words(either one) anywhere as a substring. The problem is really simple if the characters of the ...
125 views

### Languages and their relation : help

This is not a homework question though, this is something I wish to know to add to my own knowledge. While reading one of the texts on automata (K.L.P. Mishra, "Theory of Computer Science : Automata, ...
415 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 ...
53 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 ...
91 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: I'...
118 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 this....
116 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 ...
117 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 ...
715 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 ...
766 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 ...
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 ...
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 ...
35 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 ...
75 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 ...
73 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?
407 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 ...
61 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 ...
187 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 counter-...
32 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 ?
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 ...
58 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 ...
40 views

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 ...
2k 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 ...
981 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 ...
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 ...