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

learn more… | top users | synonyms

2
votes
1answer
56 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 ...
1
vote
1answer
68 views

How to prove that a language `L` is not a regular language?

Given the following question: Prove that the following language is not a regular language: A language L in alphabet $\Sigma = \{a, b\}$ where every word ...
1
vote
2answers
185 views

State diagram of DFA

I'm trying to understand how to create state diagram of DFA. I found following example. On the first diagram I dont understand why we need fourth state when third state is final and there is no ...
1
vote
0answers
43 views

how to create transition system/automata for modulo 4

I don't know how to think when to build a transition system/automata to calculate modulo 4 a of binary numbers. I know that the last two binary digits gives the rest but I need to go through hole ...
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$. ...
2
votes
0answers
42 views

Size of automata or regular expressions avoiding cross patterns

Let $\Sigma$ be an alphabet of finite size $k$, and $n$ some integer. I am interested in the language of words of size $n$ that do not contain $abab$ as a subword, for any pair $(a,b) \in \Sigma$ (I ...
1
vote
1answer
64 views

Is it possible to build an Pushdown Automata for an Ambiguous Context-Free Grammar?

Say I have the following grammar: $$S \to \epsilon \mid [S] \mid (S) \mid SS$$ This grammar is ambiguous as both the following parse trees yield the empty string $$S \to \epsilon$$ $$S \to SS \to ...
0
votes
1answer
45 views

Nondeterministic finite automaton understanding problem

It is probably a silly question but I have problem understanding it. Let's say I have to design a nondeterministic finite automaton that accepts the language consisting of words containing a string of ...
0
votes
1answer
54 views

Pushdown automaton design

I have to design a PDA that recognizes the language: $$L=\{w \mid \#(a,w) - 3\#(b,w) = 2\} $$ where $\#(a,w)$ means the number of letters $a$ in $w$ My idea is to count $a$'s and $b$'s. I have to ...
1
vote
1answer
57 views

Show a Turing Machine accepts all DFAs

You have a Turing Machine $T = \{ \{ A \} \mid A$ is a DFA and $L(A) = \Sigma^* \}$ i.e. the DFA that accepts all languages. Show it's decidable. Can you use the complement of this, the DFA that ...
0
votes
1answer
64 views

Deterministic finite automaton algorithm

I am having a little trouble understanding this question. For a DFA M = (Q, Σ, δ, q0, F), we say that a state q ∈ Q is reachable if there exists some string w ∈ Σ∗ such that q = δ∗(q0, w). Give an ...
0
votes
1answer
55 views

Pumping lemma to prove that a language is not context free

We've got $L = 0^{x^{2}}$. So we let $w = 0^{p^{2}}$, and we know that we can split w into $w = u\cdot v\cdot w\cdot x\cdot y$ , according to the pumping lemma for CFGs. I'd like to know how to ...
0
votes
1answer
314 views

CFG and PDA for w1#w2

Looking for a Context Free Grammar and Push Down Automata to describe a language made of two words, separated by a #, where the first words is not equal to the second word. For this example, we can ...
1
vote
0answers
76 views

Is this correct way to prove that { $uv$ $\mid$ $u$ and $v$ are strings over $(0,1)$ & $|u| = |v|$ } language is not regular?

I proved this using Pumping Lemma in the following way, Taking $p$ as pumping length then let us take a string $S$ where, $|u| = |v| = p$ Now according to pumping lemma $S$ can be split into three ...
0
votes
1answer
83 views

How to prove that $ \{ 0^n 1^{5n} : n \ge 10000 \} $ is not a regular language?

I proved that $$ \{0^n 1^{5n} : n \ge 0\} $$ is not a regular language using Pumping Lemma by following way. Solve by contradiction that $ L = \{ 0^n 1^{5n} : n >= 0 \}$ is regular language. ...
0
votes
0answers
223 views

Converting the NFA produced from the language $a^nb^n : n\geq 0$ to a DFA to show its regular? Leading to question about pumping lemma.

I am reading about the pumping lemma, and having a hard time understanding it. I noticed that it is used to prove a language is not regular by contradiction. So you must first prove that a language in ...
1
vote
2answers
63 views

Construct finite Automata

Im trying to construct finite automata in the form of diagrams accepting certain languages. One is in all parts the alphabet is $\{a, b\}$. Construct FA $\{w \mid w \text{ has neither $aa$ nor $bb$ ...
0
votes
1answer
31 views

Building PDA for a Language

I won't deny that this is not my homework question, but I've been thinking for a couple of hours and still have no understand $L = \{w | w ∈ \{0, 1\}^*\}$, w is a list of unary integers separated by ...
0
votes
1answer
30 views

abstract machine, what language does M accecpt?

What language does M accept? 1: {a}3 ∪ {b}3 ∪ {λ} 2: {a}3 ∪ {b}3 3: {a, b}3 ∪ {λ} 4: {a, b}3 ∪ {λ} I'm not completely sure just yet which one would work. I would appreciate it if ...
0
votes
1answer
123 views

Push Down Automata that recognizes language

I'm struggling on how to use the stack for this push down automata problem. The problem is to design a PDA that recognizes the language: $$A = \{a^ib^{2i}|\,i>0\}$$ So, we will be pushing a's onto ...
1
vote
1answer
258 views

Constructing a NFA from a right linear grammar, is this correct?

Given the right linear grammar G S -> abA | bbB | a A -> bB | aA | b B -> baB | aaaA | [Epsilon/Terminates] Is the NFA in the image below the proper ...
1
vote
1answer
165 views

Difference between a*b and a*+b? Does the “+” denote Kleene plus or “or”?

Me and a friend are study for a quiz and are trying to determine the difference between the two NFA's produce by the regular exressions a*b and ...
0
votes
2answers
187 views

Designing a deterministic finite automata

How would I go about designing a deterministic finite automata to recognize the language L = {λ, ab, abab, ababab, . . . } consisting of strings that start with ‘a’, end with ‘b’, and alternate in ...
0
votes
1answer
98 views

Deterministic finite automata [closed]

For this question about Deterministic finite automata: Is this answer: bbbb, bbba, bbab, bbaa, b, a correct?
3
votes
1answer
159 views

Challenge on Some Language and PDA

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
1
vote
1answer
57 views

Checking correctness of finite state automata designed

How to check correctness of finite state automata we have designed for a regular expression with the help of any computer program or prolog?
0
votes
1answer
61 views

Finite State Automata for (0+11+01)*(0)*(01)*

This is my homework problem and I am struggling hard for it. Can anyone please help me out? I need to find out finite state automata for (0+11+01) * (0) * (01)*. Also, if anyone can please tell me the ...
0
votes
1answer
35 views

Proving non-regularity of a language

How can I prove $L = (01^n2^n | n\geq 0)$ is not regular? Would it be sufficient to say that $01^p2^p$ is in $L$ and by pumping lemma, $01^p2^p$ can be written as $xyz$ such that $|y|>0, ...
0
votes
1answer
113 views

equivalence class for language in Theory of automata

we say x,y is equivalent to language L, if for any $z \in L$ we have: $xz \in L \Longleftrightarrow yz \in L$. for $ L= (ab \cup aab)^* $, what is the equivalence class for L? my professor ...
0
votes
2answers
658 views

Input and output of a Turing machine

For some machine models of computation there is no question what their input and output is: it's just the contents of some specific "cells", e.g. on a "tape" isomorphic to $\mathbb{N}$. Consider for ...
0
votes
1answer
118 views

Use the power-set construction to find a deterministic automata

Given a nondeterministc automata N, how do you use the power-set construction to find a deterministic automata that recognizes L(N)? Here is my work so far: We can start in state 1, 2. If we get ...
3
votes
1answer
39 views

Why is $\left\{a\right\}^*\cap L(A)=\emptyset$? where $\delta(q,a)=q$

I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below : Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all states ...
0
votes
1answer
137 views

how to draw this DFA?

{w belongs to all string patterns as a^i b^j a^k | i+j=even and j+k =odd} draw a DFA and find its regular language. please note here, i have put comma in between the format of aba string just for ...
0
votes
1answer
110 views

How can a DFA corresponding to an NFA have a transition that the original NFA does not?

First sorry for the poor pictures, but I think they are ok enough to get the point across. I would like to see the steps involved to convert this NFA to a DFA using the method explained in this ...
0
votes
1answer
61 views

Soft question, Understanding NFAs and DFAs; Requirements for either.

I have a few quick questions about NFAs and DFAs. Is any automaton with epsilon transitions always a NFA? Is any automaton with two paths for the same symbol from a state always a NFA? Ex. Say state ...
0
votes
2answers
60 views

Regular Expression Similarity Check

I was solving Formal Language and Automata Theory for a competitive exam, whence I came upon this following question: The regular expression 0*(10*)* denotes same set as: 0(0+10)* (0+1)10(0+1) ...
3
votes
2answers
292 views

Is a DFA a subset of NFA? Why?

After reading this previous question Difference between NFA and DFA, it's clearer to me their relationship/differences. Can one say that a DFA is a subset of a NFA where both recognize a/the same ...
0
votes
0answers
84 views

Number of states of a finite automaton recognizing all words beginning with some fixed string $x$

For a string $x \in \{a,b\}^\ast$ with $|x| = n$, how many states are required for an FA accepting the language of all strings in $\{a,b\}$ that begin with $x$? For each of these states, describe the ...
1
vote
1answer
13 views

Find a state machine or a regex that accept the following language description

The alphabet of the language L is {a, b} and there has to be an even number of both a's and b's but no other restrictions apply. I've been at this for over an hour, drawing state machines that lead ...
-2
votes
1answer
661 views

FA that accepts only those words that have an even number of substrings cdc?

I take this question as it could accept cdccdc,cdccdccdccdc,dddcdccdc,etc. I feel that I coveed all the even loops of cdccdc but I am stuck trying to figure out how to add in c* and d* in the mix of ...
0
votes
1answer
155 views

Turing Machine Problem

We know, A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules I Draw a TM for input $x=(0+1)^*$ i want to implement ...
2
votes
1answer
76 views

$L=${$a^nb^nc^n : n \geq 0 $} CFG Recognizing

Suppose $L=${$a^nb^nc^n : n \geq 0 $} and I. $h(L), h(a)=a, h(b)=bb, h(c)=b$ II. $L^R$ III. $L^*$ IV. $h(L), h(a)=a, h(b)=bb, h(c)=a$ Why just I is a CFG and other is not? anyone can help me to ...
0
votes
2answers
124 views

Language of a grammar vs regular expression vs nfa

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
1
vote
1answer
44 views

context free grammar that describes even numbers

I am learning about context-free grammars and as a toy example I wanted to design one that describes binary digits ending with 0. My attempt : S -> 1S | 0S | e0 - where e is the empty string. Is this ...
-1
votes
1answer
108 views

PDA and Some language Grammar inference

L1={$w^* $| w=x and $ x \in \Sigma^*$} L2={$ww^R ww^R $| $ w \in ( \Sigma + \Sigma)^*$} L3={$w | w=xy, x,y \in \Sigma^*$, y is a substring of x} a) there is a PDA(push down automata) that accept ...
0
votes
1answer
51 views

Pushdown Automata and Challenge in Grammar

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
3
votes
0answers
48 views

Lattice worms with nontrivial deaths

In Paterson's worms, a triangular lattice is used. A worm can move in 6 directions. As each node is hit, the worm follows an internal rule for which edge it will eat next based on the edges already ...
1
vote
1answer
60 views

Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
0
votes
1answer
52 views

A CFG Grammar for One Language

Suppose : $w_1,w_2 \in \{a,b\}^∗$ and $ L=\{w_1w_2 \mid w_1,w_2 \in \{a,b\}^* \land n_a(w_1)=n_b(w_2)\}$ $n_a$ is number of $a$'s and $n_b$ is number of $b$'s. This is a Entrance Exam question. I ...
0
votes
1answer
72 views

Challenge on Property of Complement in Language

We have: and M be a finite automata. Suppose d(M) be a deterministic automata that equivalence to M. if $M_1$ and $M_2$ be two finite automata, $M_1 + M_2$ is the finite automata such that the ...