# Tagged Questions

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

147 views

### pumping lemma for CFL vs pumping lemma for regular languages

Is the pumping lemma for context free languages a generalization of the pumping lemma for regular languages (for instance if we set $u=\epsilon, v=\epsilon$ we can then relate $wx$ in the pumping ...
168 views

### Quick question on DFA

I'm asked to list all DFA over the alphabet sigma = {0} such that the set of states is {s0, s1}, for which the initial state is s0 and the set of accept states is either {s0} or {s1}. And also asked ...
62 views

49 views

### Context-free language or not

It is language: $L = \left\lbrace a^ib^jc^kd^l \mid i+k < j+l+3 \right\rbrace$ Is it context-free or not? I have two versions: 1)Pumping lemma(refute): get a word $uvxyz = aabcd$ if $i=2$ we get ...
69 views

### Minimum Size of DFA

I'm confused about the following DFA problem: Let L denote the set of all strings in $\{a, b\}^∗$ that contain abb or aab as a substring. Show that any DFA that decides L must have at least five ...
73 views

### Proving from Myhill-Nerode that the minimum DFA is the smallest automaton recognizing $L$

From this paper, In the proof of (Myhill-Nerode theorem) it's stated that if $L$ is a regular language and the index of $\sim_L$ is $i_L \in \mathbb{N}$ then it's both necessary and sufficient for ...
205 views

### Context free grammar $\{a^n b^m c^k\; : \;k>m \; \; k>n\}$

Is this a CFL? $$\{a^n b^m c^k\; : \;k>m \; \; k>n\}$$ When on seeing $a$'s and $b$'s I push them onto stack and as I see $c$ as input if $TOS$ is $b$ ,I pop them ,again if $TOS$ is a,I pop ...
190 views

### Construct a deterministic finite state automaton

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10. This is what I drew. Not sure if its correct. State 2 is the final state. Am I missing ...
148 views

### Find the language recognized by the given deterministic finite state automaton

I got 01* U 1(01)01 as my answer. I'm not sure if its right.
126 views

### How to find the right quotient of a language given two languages?

If $L_1= \{a^n b^m \mid n \geqslant 1, m \geqslant 1 \} \cup \{ba\}$ and $L_2= \{b^m \mid m \geqslant 0 \}$. I am not getting how the DFA for $L_1/L_2$ is constructed in the second figure using ...
52 views

31 views

### Explain the semantics of concurrent languages with real analysis examples

In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. I need to explain the concurrency ...
413 views

### Determinitic finite automaton (DFA) that accepts natural numbers divisible by 6

I'm new to Formal Systems and Automata and I'm working on some exercises to get familiar with the concepts. I want to create a DFA that accepts natural numbers divisible by 6. I know that a number ...
66 views

### NFA (nondeterministic finite automaton) made out of the Bible?

Let B be the language over alphabet {a, ... z} consisting of those words occuring in the Bible. Thus, B = {in,the,beginning,god,created,...}. Describe an NFA whose language is B. Describe what ...
50 views

### Write grammar for given language

I'm trying to write a grammar for the language below: $$(a+b)^*−\{𝑤𝑤𝑤 ∶ 𝑤\in\{a,b\}^*\}$$ could anyone help me?
49 views

### what do we mean by saying that a particular computing machine is more powerful than another computing machine?

I am having confusion in understanding the concept of the word "powerful" in automata theory. Even the confusion arises that if I have a DFA with single final state ,so then is it more or less ...
41 views

### Is $L = \{0^{i}1^{i}0^{j}1^{i} | i, j > 0\}$ a context free language?

Is the following argument correct? $L = (A \circ B) \cap C$ where, $A = \{0^{i}1^{i}$ $|$ $i > 0\}$ $B = \{0^{j}1^{i}$ $|$ $i, j > 0\}$ $C = \{0^{i}1^{j}0^{k}1^{i}$ $|$ $i, j, k > 0\}$ We ...
2k views

### What is the easiest way to determine the accepted language of a deterministic finite automaton (DFA)?

I'm new to automata theory and I'm currently working on some exercises on determining the accepted language of DFAs. I was wondering whether there exists some clever strategy to determine the accepted ...
35 views

### Transition function of the generalized nondeterministic finite automata

Why does the transition function of a GNFA map from two states to a regular expression $$\delta: (Q \setminus \{q_{start}\}) \times (Q \setminus \{q_{accept}\}) \to R$$ instead of mapping from the ...
66 views

### A Regular Expression for all strings that…

I got a problem I have to solve, the problem says that given an alphabet $\Sigma = \{a, b, c\}$ I have to build a regular expression that describes the string with: An even number of a's. A 4k + 1 ...
18 views

### Where does $b(10)$ goes under this automaton

This is finite state automaton for Grigorchuk group. I have never studied automaton formally, so I wanna check is it fine the way I am doing it. Here $\epsilon$ change the first entry on string from ...
95 views

177 views

### How to construct a DFA for truncate the rightmost symbol from a given string?

If I have a truncate operation defined which removes the rightmost symbol from a string ,for instance I have a string say aababb so it removes the rightmost symbol b and the output is aabab. so how ...
154 views

### How can a Moore machine be converted into an equivalent Mealy machine and vice versa?

Moore machine is a finite-state machine whose output values are determined by its current state only. Mealy machine is a finite-state machine whose output values are determined both by its current ...
77 views

### Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
486 views

### How to construct the DFA for the following question?

Given $L=\{ab^5 w b^4 \}$ where $w=\{a,b\}^*$. I am not able to construct it, I tried it but getting problems with the transitions for input symbol a.
70 views

### Learning finite automata from symbol set and given sample

Good day. We have a finite automaton F1, for example, . We need to get automaton F2 that accepts strings like accepted by <...
144 views

### NFA to DFA and Regular Expression

The truth is that my teacher gave us a homework, and I wanted to ask you if I did this right. What I have to do is answer the following questions given the following NFA. Why is this an NFA? What ...
280 views

### nth-root of continued fraction with Raney transducers

There are some algorithms for doing basic arithmetic by using regular continued fraction expansions. These algorithms are mainly due to Gosper (1972) and Raney (1973). These two approaches use (bi)...