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

learn more… | top users | synonyms

0
votes
0answers
14 views

generating transition diagram and accepted language from prime number expression

I have the following expression and have to generate the diagram $(M(5))$ and accepted language $(M(5))$ for it, the issue is that I am having trouble even understanding what the expression is saying. ...
4
votes
2answers
39 views

Pumping Lemma for $L= \{a^{m}b^{n}| m,n > 0 , \gcd(m,n) > 1 \}$

Let language $L= \{a^mb^n \mid m,n > 0 , \gcd(m,n) > 1\} $ above the alphabet $\Sigma = \{a,b\} $ . I need to prove by the pumping lemma that $L$ is not a regular language but I am having ...
0
votes
0answers
23 views

How to derive Turing Machine language?

Say you're given a TM (Turing Machine) $M = (Q, \Sigma, \Gamma, \vdash, \sqcup, \Diamond)$ and given the partial $\delta$: $$\begin{array}{c|cc} ...
1
vote
0answers
14 views

How to make the NDPA of this question?

Say $w^R $ is the reverse of $w$. E.g.: $\epsilon^R = \epsilon$ and $(abbab)^R = babba$ Now say $L = \{ww^R | w \in L (a^*b^*)\}$ Draw the NDPA $M$ with $L(M) = M$ I understand NDPA's, however I ...
1
vote
2answers
28 views

equivalent regular expr

Given a regular expression $r_1$, is $(r_1^*)^* = (r_1^*)$. I know that this is true but I do not know how to prove it. Would it be adequate to set $r_1$ to a regular expression such as $(a+b)$ for ...
0
votes
1answer
25 views

Prove that there exists an equivalent grammar in Chomsky Normal Form like $G'$ such that $G'$ has at most $(K-1)|P|+|T|$ production rules

A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate patterns of strings. A CFG consists of the following components: a set of terminal symbols, which ...
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 ...
0
votes
1answer
1k views

Create DFA that accept language where number of 0's is even and after every 1 goes 0

Alphabet ${} = \{0,1\}$. Language $L = \{ w \in \{0,1\}^* \mid \text{ number of $0$'s in $w$ is even and after every $1$ goes $0$} \}$. I'm trying to create DFA that accepts language $L$. ...
0
votes
2answers
625 views

Using the Pumping Lemma to Prove $L = \{a^ib^jc^k \mid i < j < k\}$ is not Context-Free

I want to use the Pumping Lemma to prove that $$L = \{a^ib^jc^k \mid i < j < k\}$$ is not context-free. I think I have the intuition, but I don't know how to prove it. Help?
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?
1
vote
1answer
27 views

relation on Languages of one finite machine !?

I adopted this question from 2013 Final Entrance Exam on CS. We have Finite Machine $M$ and Languages $L_1$ to $L_4$ as depicted in following picture: The question is which of the $A$ to $D$ ...
0
votes
0answers
17 views

How to decompose a Finite State Machine (FSM) into a cascade of two or more FSMs?

I am coming from Electrical Engineering background and would like to know how can I decompose a given FSM into a cascade of two or more FSMs. To be more precise, I am looking at following questions ...
0
votes
0answers
27 views

is this grammar ambiguous? and what is the recursive inference, the leftmost derivation and the parse tree for the word abcddd?

first question is, is this grammar ambiguous? how can i show that is there a way? and second question is what is the recursive inference, the leftmost derivation and the parse tree for the word ...
0
votes
1answer
31 views

Give a context-free grammar that generates the language

Give a context-free grammar that generates the language: $\{a^i b^j c^k d^h \mid i, j, h \geq 0, k>0 \text{ and } i+j \leq h\}$ This is what I've done so far: $S \rightarrow aSb \mid bSc \mid ...
5
votes
2answers
4k 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^* \}$
1
vote
0answers
32 views

Find $A^n$ for n=0,1, and 3: Languages and Finite State Machines

The question is: Let $A$={11,00}. Find $A^n$ for n=0,1, and 3. Would i be right in thinking that $A^0$ = {λ} $A^1$ = {11,00} $A^3$ = {111111,111100,110011,110000,000011,000000,001100,001111}. if ...
-1
votes
0answers
70 views

Find $A^n$ for n=0,1, and 3: Languages and FSM

I am having trouble trying to work out this finite state machine and languages question. Let $A=\{11,00\}$. Find $A^n$ for $n=0,1, 3$. Where would I begin?
0
votes
0answers
19 views

What is an automata network?

I've tried Wikipedia and Google as first steps, but while I've found some interesting papers and articles, and a couple expensive textbooks, I've yet to find a clear definition of an automata network ...
0
votes
1answer
401 views

Understanding how to convert a PDA to a CFG

Given a PDA, initialized with $\#$ on the stack, and with accepting states $q_a, q_b, q_c$ and the following transitions: (current state, stack head, input character, replacement for old stack head, ...
0
votes
1answer
50 views

What's the meaning this DOT notation?

I'm reading a chapter in a Model Checking book. I came across this chapter "Symbolic Model Checking", in which the author mentions Fixed Point representation. I don't know how to explain the context, ...
5
votes
2answers
42 views

Can a regular grammar be ambiguous?

An ambiguous grammar is a context-free grammar for which there exists a string that has more than one leftmost derivation, while an unambiguous grammar is a context-free grammar for which every valid ...
0
votes
1answer
17 views

accepted language notation for CFG for recurring 1's and 0's

Hi I often have trouble with the notation when having to write the accepted language for a finite automata or CFG. Right know I have a CFG that generates groups of any number of 1's followed by any ...
0
votes
0answers
7 views

What is the instruction for the following PDA?

I don't understand why there is a push(a,X,a) but then there is no pop - a instruction.
1
vote
1answer
71 views

Attractors of a Random Boolean Network?

I need some direction on the topic of Random boolean networks (NK-boolean networks or Kauffman automata). I know some of the results like if K=1 the systems settles down to fixed points, if K=2 it ...
1
vote
2answers
25 views

Give a regular expression

Let Σ be {0, 1} Give a regular expression generating words over Σ containing an even number of 1’s or with a length which is multiple of 3. i came up with this solution: ε ( ((0*(10*10*)) + ((0+1) ...
1
vote
2answers
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..
0
votes
0answers
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 ...
0
votes
1answer
36 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
votes
4answers
44k views

Difference between NFA and DFA

In very simple terms please, all resources I'm finding are talking about tuples and stuff and I just need a simple explanation that I can remember easily because I keep getting them mixed up.
0
votes
0answers
24 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 ...
0
votes
1answer
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 ...
0
votes
1answer
35 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 ...
0
votes
1answer
22 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 ...
0
votes
1answer
23 views

Prove that $even(L)$ is regular

For any string $w$, define $even(w)$ to be the string that results from deleting all the letters that occur in odd positions of $w$. For example, $even(a)=ε$, $even(ab)=b$, $even(acb) = c$, and ...
0
votes
1answer
48 views

Give a NFA over the alphabet {a ,b , c}

How do I solve this? Give a NFA over the alphabet {a, b, c} whose words have a length which is multiple of 4 or are such that the number of a’a plus the number of b’s in the word is even. Use then ...
1
vote
1answer
67 views

Is the language of complex numbers regular?

A complex number is a number that can be expressed in the form $a + bi$, where $a$ and $b$ are real numbers and i is the imaginary unit, that satisfies the equation $i^2 = −1$. In this expression, $a$ ...
0
votes
1answer
18 views

If $L_1.L_2$ is regular, and $L_1$ is regular, then $L_2$ is regular

A regular language (also called a rational language) is a formal language that can be expressed using a regular expression. Now, Is this true? Assume that $L=L_1.L_2$ is a regular language. Also ...
-1
votes
1answer
174 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 ...
0
votes
0answers
14 views

Constructing a grammar for language of all squared words

I need help in constructing a grammar for this language: $L = \{ \alpha \in \{a\}^* \mid \alpha = a^{n^2}, n \in \mathbb{N}_0\}$ All I can tell about $L$ is that it should be at least context-free. ...
1
vote
1answer
46 views

Find an LL(2) grammar for the following language

The question asks to find both an LL(1) and an LL(2) grammar for the following language {𝑎^𝑚 𝑏^𝑛 𝑐^𝑚+𝑛 | m,n ϵ N} I have an LL(1) grammar like so ...
1
vote
1answer
29 views

A grammar for the complement of language $L=\{a^{t+3}b^t:t \ge 0\}$

Assume that the language $L=\{a^{t+3}b^t:t \ge 0\}$ is given. Q1 : How can we write a grammar for the complement of this language? Q2 : Assume that $L'=\{a^nb^m:n\ge0,m\gt n\}$ is given. Can you ...
1
vote
1answer
85 views

Minimal DFA for a given regular expression

How can I construct a minimal DFA from the following definition? $L=\{w \in \{a,b,c\}^* $: if the second-to-last letter from w is an $a$, then the number of $c$'s $\le 1\}$ I've already made a ...
1
vote
3answers
46 views

Trying to convert DFA to regular expression

I'm trying to write a regular expression from this DFA but I'm having some trouble. I can tell you what I've done so far: I started by adding a new beginning state and a new final state because ...
0
votes
1answer
19 views

A regular expression for the language $L=\{w \in \{a,b\}^*:n_a(w)=3 \land n_b(w)=4\}$

A language like $L=\{w \in \{a,b\}^*:n_a(w)=3 \land n_b(w)=4\}$ is given. The first question : Is this language regular? The second question : If $L$ is regular, How can we write a regular ...
2
votes
4answers
1k 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
30 views

Finding the language of a finite automaton

Is there any formal and elegant way of finding the language of a finite automaton? For example, It's trivial that the language accepted by the following diagram of the automaton $A$ is $L(A) = (a ...
0
votes
1answer
52 views

Design Turing Machine

Design a single-tape Turing machine with input alphabet {0, 1} to decide the language $$\{ x\in\{0,1\}^* \mid \#(0,x)=2\cdot\#(1,x)\}.$$ Could someone give me clarification on how to approach and ...
0
votes
0answers
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$ ...
0
votes
1answer
2k views

Reachability graph for Petri net.

I am trying to draw a reachability graph for this Petri net. Could you please help me to understand how this works?
0
votes
0answers
28 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 ...