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

learn more… | top users | synonyms

5
votes
2answers
3k views

How to show that $ALL_{DFA}$ is in P

How can I show that $ALL_{DFA}$ is in P ? $ALL_{DFA} = \{ \langle A \rangle \mid A \text{ is a DFA and } L(A) = \Sigma^* \}$
0
votes
0answers
26 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 ...
-1
votes
0answers
11 views
1
vote
1answer
42 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 ...
1
vote
1answer
37 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?
1
vote
1answer
315 views

Context free grammar to pushdown automata…

<expr> −→ <term> | <expr> + <term> <term> −→ <factor> | <term> × <factor> <factor> −→ (<expr>) | b ...
0
votes
0answers
33 views

Is the sequence $(v_p(n))$ of $p$-adic valuations of positive integers the fixed point of a morphism, for every prime $p$?

Fix a prime number $p$ and consider the sequence $\mathbf{v}_p = (v_p(n))_{n \geq 1}$, where $v_p$ is the usual $p$-adic valuation, i.e. $v_p(n) = a$ iff $p^a \parallel n$. While browsing the OEIS I ...
0
votes
1answer
34 views

Convert the regular expression to a NFA

I have to convert the following regular expressions to a NFA: $$(0 \cup 1)^{\star} 000 (0 \cup 1)^{\star}$$ $$(((00)^{\star} (11)) \cup 01)^{\star}$$ $$\emptyset^{\star}$$ $$a(abb)^{\star} \cup ...
1
vote
1answer
25 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 ...
1
vote
1answer
25 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 ...
2
votes
3answers
197 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 ...
1
vote
1answer
21 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 ...
2
votes
2answers
30 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 ...
0
votes
1answer
201 views

How to convert this NFA to DFA?

What are the steps for converting this NFA to a DFA??
0
votes
0answers
12 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 ...
2
votes
0answers
50 views

How to show $L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ is ambiguous?

I'm recently familiar with this site and prefer to ask a very hard problem :) How can we prove that the following language is inherently ambiguous? $$L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m ...
0
votes
1answer
33 views

How to prove the language of all binary numbers that are prime is nonregular using pumping lemma?

How to prove the language of all binary numbers that are prime is not regular using pumping lemma? I have seen Can an infinite set of primes be a regular language or CFG? We have not studied the ...
1
vote
1answer
45 views

Is it possible to write an Unambiguous Grammar for Two Hard Language ?!?

I came across a very hard interview exam. It was asked wrote an unambiguous grammar for two following language, Who can hint it to solve it? 1) $L = \{a^n b^{2n} c: n\geq 0\} \cup \{a^{2n} b^n d: ...
1
vote
0answers
36 views

Where is my mistake in this DFA minimization?

I'm currently having trouble minimizing my DFA. I have the following graph: (ignore the numbers after ":") Using the table minimization method I reached: (x is distinguishable, O is ...
2
votes
2answers
252 views

how to prove that the following is not a regular language?

the language we want to disprove is : $$ L = \{ 0^i1^j| gcd(i,j)=1 \} $$ my attempt : i used the pumping lemma this way: consider the set of strings of the form $0^p1^q$ such that $n <=p$ and ...
1
vote
0answers
47 views

Show that language $L'$ is regular given $L$ is regular

I show you some solution and I ask you for looking at it. $L'=\{y|\exists_{z,x} xyz\in L\wedge |x|=|y|=|z|\}$ Automaton for language $L$: $M=(Q,\Sigma, \delta, q_0, F)$ For language $L':$ $M'=(Q', ...
-1
votes
1answer
22 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 ...
2
votes
1answer
34 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 ...
2
votes
0answers
60 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 ...
1
vote
2answers
72 views

Prove the following by using mathematical induction

If we define the alphabet such that $$ \Sigma = {\{a,b}\} $$ and let $w$ be a string over it. I'd like to prove $$ ( \operatorname{comp}(w))^R = \operatorname{comp}(w^R) $$ where $$ w^R$$ and ...
0
votes
2answers
74 views

Determining whether a language belongs to R or RE (Turing Machines)

Let $$ L = \{ \langle M\rangle \mid \text{$M$ is a Turing machine that accepts a string $w$ if and only if it accepts $w^R$}\} $$ Does the language $L$ belong to R, RE or neither? In each case, why? ...
1
vote
2answers
28 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.
2
votes
1answer
79 views

Determine the language that corresponds to the following automata.

I want to determine that language that corresponds to the following automata Note: $q_{6}$ have arrow to $a$ to himself. I started with the minimal words: $aaabb$ $aaba$ $aaaba$ $bababa$ the ...
0
votes
1answer
52 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 ...
1
vote
0answers
76 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 ...
2
votes
1answer
30 views

Show that the function floor-log is primitive recursive

I have been stuck on this problem for a while and I was hoping someone could help me with it. This is for my computer science automata and formal languages class. Given an integer $b$ greater than or ...
2
votes
1answer
42 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 ...
0
votes
1answer
56 views

Pushdown Automata formal definition, L(M), tracing input

Let M be a deterministic PDA with the transition function d: ...
2
votes
1answer
20 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, ...
0
votes
1answer
29 views

Push Down Automata

I've been stuck on this one problem for a couple of days now with no clue on how to complete it. Construct a PDA which accepts precisely the language $\{a^{2n} (bc)^n\mid n \in \mathbb{N}\}$. ...
0
votes
1answer
39 views

Proving an operation is closed under regular languages

Following operation is defined over languages where $n \in \mathbb{N} :$ $L \ominus n = \lbrace s \in \sum^* | \exists s^{'} \in \sum^* (length(s^{'})=n,ss^{'} \in L) \rbrace$ Meaning that $L ...
0
votes
0answers
107 views

Automata to detect numbers divisible by $7$

I have a task and I really have no idea how to solve it. Build deterministic finite automata such that it can detect numbers divisible by $7$. So our alphabet is $\left\{0,1,2,3,4,5,6,7,8,9\right\}$ ...
0
votes
0answers
19 views

How to prove that Pumping lemma can't be used to prove regular languages.

I need a prove that pumping lemma can't be used to prove regular language. Pumping lemma is only used for proving non-regular language, but I need to show that how it can't be used to prove regular ...
-1
votes
2answers
30 views

How to Solve Complex Non-Regular Language? [closed]

$L_5={\{ c^n a^m b^p,n+m=p,p≥6}\}$ where $∑=(a,b,c)$ I need little help, I was practicing Pumping lemma, and I encountered this language, I saw these conditions and I got totally confused, what to do ...
0
votes
1answer
19 views

Are these languages Regular or Non-regular?

I have these two languages $L={\{a^n b^m,n≥m+5,m>0}\}$ Where $∑=(a,b)$ $L={\{a^n b^m,n≥m+5,m≤5}\}$ Where $∑=(a,b)$ As you can see that there is only one difference, the condition of ...
1
vote
2answers
43 views

Why |w|>=m in pumping lemma?

If L is a regular language, then there exists a constant n (which depends on L) such that ...
0
votes
1answer
21 views

Why does this concatenation doesn't work for these 2 dfa's [closed]

I have the following deterministic finite automaton which accepts an even number of 0's. and this automaton which accepts an odd number of 1's: I want to concatenate these 2 automatons. I ...
1
vote
1answer
22 views

Two DFA to one NFA.

Let assume that I have given DFA $D$ which recognize language $L$. Now I would like create the DFA/NFA which recognize the language $L'$. $$ L' = \{ w \in L : |w| = 2k, k \ge 0 \}$$ In words, $L'$ ...
0
votes
0answers
27 views

Theory automata. Proof. [duplicate]

Let $A/B= \{ w : wx \in A \}$ for some $x \in B $. Show that if $A$ is regular and $B$ is any language, then $A/B$ is regular. Please hint me with doing it using Myhill-Nerod's theorem. I observed ...
-1
votes
2answers
24 views

Decomposing an infinite regular language

Let $L$ be an infinite regular language. Prove that $L$ can be split up into $L_1, L_2$, so that $L_1 \cup L_2 = L$ and $L_1 \cap L_2 = \emptyset$ Can you give me some directions to do it? Thanks ...
1
vote
1answer
491 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
1
vote
2answers
32 views

Convert NFA to DFA

I have to convert the following NFA's into the equivalent DFA's. I have done the following: Could you tell me if it is correct??
1
vote
1answer
32 views

Write the regular expression of the language that the DFA accepts.

I am given a DFA and I have tried to write the regular expression of the language that it accepts. This is the DFA that I am given: I have found some words that the DFA accepts: ...
0
votes
2answers
33 views

Finding the regular expression

I have the problem below: I need to find the regular expression of the set of strings where $n(a)+n(b)$ is an even number (where $n(a)$ is the number of $a$'s and $n(b)$ is the number of $b$'s) .. I ...
0
votes
2answers
64 views

Determine whether $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ is regular.

Given the alphabet $\Sigma=\{a, b\}$ and for the next Language $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ determine whether the language is regular. Firstly, I think this language is regular. ...