# Tagged Questions

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

8 views

### How to find transition matrix in cascaded FSMs?

I am considering a 4-state system Equivalently, I can use a cascade approach to represent the same system as In cascade approach, If I consider independent condition on input on both subsystems,...
24 views

### NFA without ε-transitions which recognizes the language generated by the regular expression

NFA without ε-transitions which recognises the language generated by the regular expression: 1(0 + 0(10)*0)0 here is what i've done so far..
37 views

### Is the problem decidable with Turing machine M that inputs x,y,z does M halts on these 3 instances

Is the following problem is decidable? Given a Turing machine M inputs x,y,z does M halts on these 3 instances? Hint: make y and z any two artificial inputs that the program stops with these inputs. ...
25 views

### NFA Correctness

Hello I have the following instructions: L3 is all strings where (i) the number of $b$'s is twice the number of $a$'s, and (ii) each substring with three occurrences of $a$ and $b$ should contain ...
36 views

### Deterministic finite automaton parity bit question

for a university assignment ive been tasked with creating a DFA that accepts the regular language (00010 + 1101 + 1010)* and must contain a parity bit at the end to make sure there is an even amount ...
23 views

### Problem in Understanding the DFA, Need Help

I am reading Hopcroft Ullman - Automata Theory(2nd Edition). In page Number 65 (Red Underline part in the given Image); I understand when i=1 but unable to understand when i>1 then how the Accepting ...
23 views

### Regularity check of languages

L1 will not be CFL also as it needs more than one stack to count. L1/L2 gives concatenation and the result will be $a^{n} b^{2n} c^{4n}$ which is again non regular. Am I right? I am little bit ...
23 views

15 views

### Pupming lemma for CFG in alternative normal form

Let us say that a CFG is given in the following normal form where every production is of either type Non-terminal $\rightarrow$ Non-terminal Non-terminal Non-terminal Non-terminal $\rightarrow$ ...
33 views

### Convert a PDA to a CFG

My professor doesn't do a very good job at explaining the process of converting a PDA to a CFG. Can someone help explain it? The way I see it (but it produces wrong results) is each production is ...
31 views

### How do I describe the following DFA

Consider the alphabet E = ${[abc] : a, b, c \in 0,1,...,9)}$ Example [234], [567], [897] are symbols of the alphabet. For a string $w \in$ let n($w$) denote the number represented by $w$: ...
22 views

### turing machine decidable description for the language

L = { | R is a regular expression that produces at least one word in {a, b} * which contains a symbol exactly 3 times} ...
38 views

### turing machine decidability language

I must show that this language is decidable but I think it's not {D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ } Here what I think I give a reduction from E(TM). I suppose that this ...
28 views

### Deterministic vs nondeterministic finite automata

I've just asked a question about non-deterministic finite automata but still feel confused. Here is the attached Deterministic Finite Automata: Deterministic diagram The first node has two ...
31 views

### I have a proposal on recursive functions, but I need a second voice to be sure it makes sense.

My main field is computer science. Although I am mostly familiar with computer science theory, I lack in math theory. So, to an average computer scientist, the term ‘recursive function’ will invoke ...
25 views

### A regular expression for the language $L=\{w:(n_a(w)-n_b(w))mod3=1\}$

Assume a language like $L=\{w:(n_a(w)-n_b(w))mod3=1\}$ is given. How can i find a regular expression for this language using a systematic process? Note : I can easily draw a DFA accepting this ...
21 views

### What ω-language does a Büchi Automaton recognize?

When I'm reading about Büchi Automatons, it says that x is accepted if there are infinitely many occurrences of states from the set of accepting states in the run. But for instance, when I'm being ...
35 views

### non-deterministic automaton and regular expression

I am a linguistics and I start to read some books about Nlp. I have to design a non-deterministic automaton and regular expression over the alphabet $\{a,b,c\}$ that accept all and only those strings ...
16 views

### Verify correctness of this PDA

I'm trying to construct a PDA for the language $\{a,b\}$ where there are the same number of $a$'s as $b$'s. This is what I have, but I'm skeptical on the correctness. Can anyone verify?
54 views

### Turing machine macro notation

This is an example from the book Automata, Computability and Complexity by Elaine Rich. Macro language is defined as follows: (screenshot from the book) And these are the steps mentioned : Scan ...
206 views

### Deterministic finite automata (DFA) (have odd length or end with aaa)

Is my attempt is true or where am I wrong? DFA : The set of strings over $\{a, b\}$ that have odd length or end with $aaa$.
160 views

### Finite automata NFA

How can I construct finite automata accepting the following language? NFA : The set of strings over $\{a, b\}$ in which every $a$ is followed by $b$ or $ab$. My try
55 views

### Automata homomorphism relation

We have the following automata $A$: My task is to find automata $B$ and $C$ such that both of them admit a homomorphism to $A$, but $B$ is not homomorphic to $C$ and vice versa. So far, we know ...
303 views

### Show that $\{a^ib^jc^{2j}\mid i\ge 0,j\ge 0\}$ is not regular

How can I show this?I don't know how to start. Show that the set given below is not regular. $$\{a^ib^jc^{2j}\mid i\ge 0,j\ge 0\}$$
90 views

### What is flaw on my proof to identify any string of $L_2$ using single stack?
Consider the following languages: $L_1=\{a^nb^mc^{n+m}:m,n≥1\}$ $L_2=\{a^nb^nc^{2n}:n≥1\}$ Which one of the following is TRUE? Both $L_1$ and $L_2$ are context-free. $L_1$ is context-free while ...